#import<fstream>
using namespace std;ifstream f("divprim.in");ofstream g("divprim.out");int m[1000002][8],p[1000002],i,j,n,a,b;main(){for(i=2;i<1000001;m[i][p[i]]=i,++i){if(!p[i]){for(j=i;j<1000001;++p[j],j+=i);}for(j=1;j<8;m[i][j]=m[i-1][j],++j);}f>>n;while(n--){f>>a>>b,g<<m[a][b]<<'\n';}}