#include <fstream>
#include <vector>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int ciur[1000001];
int main()
{
    int t,n,k;
    for(int i=2; i<=1000000; i++){
        if(ciur[i]==0){
            for(int j=i; j<=1000000; j+=i){
                ciur[j]++;
            }
        }
    }
    vector<int> numar[8];
    for(int i=0; i<8; i++){
        numar[i].push_back(0);
    }
    for(int i=0; i<=1000000; i++){
        numar[ciur[i]].push_back(i);
    }
    fin>>t;
    for(int i=0; i<t; i++){
        fin>>n>>k;
        int st=0,dr,mij;
        dr=numar[k].size()-1;
        while(st<dr){
            mij=(st+dr+1)/2;
            if(numar[k][mij]>n){
                dr=mij-1;
            }
            if(numar[k][mij]<=n){
                st=mij;
            }
        }
        fout<<numar[k][st]<<"\n";
    }

    return 0;
}