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