# include <fstream>
# define DIM 1000010
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int f[DIM],v[8][DIM],n,k,t,i,j;
int main () {
    for(i=2;i<=DIM-5;i++){
        if(f[i]==0)
            for(j=i;j<=DIM-5;j+=i)
                f[j]++;
            v[f[i]][i]=i;
    }
    for(j=0;j<8;j++)
        for(i=1;i<=DIM-5;i++)
            if(v[j][i]==0)
                v[j][i]=v[j][i-1];
    fin>>t;
    for(i=1;i<=t;i++){
        fin>>n>>k;
        fout<<v[k][n]<<"\n";
    }
    return 0;
}