#include<stdio.h>
#define maxn 1100005
#define maxp 1000000
long long i,j,t,a[maxn],k,p,sol[maxn][10];
FILE *f, *g;
int main()
{f=fopen("divprim.in","r");
g=fopen("divprim.out","w");
for(i=2;i<maxp;i++)
if(a[i]==0)
{for(j=i;j<=maxp;j+=i)
a[j]++;}
for(i=2;i<=maxp;i++)
if(a[i]<=7)
sol[i][a[i]]=i;
for(i=2;i<=maxp;i++)
for(j=1;j<=8;j++)
if(sol[i][j]==0)
sol[i][j]=sol[i-1][j];
fscanf(f,"%lld",&t);
for(i=1;i<=t;i++)
{fscanf(f,"%lld %lld",&p,&k);
fprintf(g,"%lld\n",sol[p][k]);}
fclose(f);
fclose(g);
return 0;}