#include<stdio.h>
#define maxn 1000005
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<maxn;i++)
if(a[i]==0)
{for(j=i;j<=maxn;j+=i)
a[j]++;}
for(i=2;i<=maxn;i++)
if(a[i]<=7)
sol[i][a[i]]=i;
for(i=2;i<=maxn;i++)
for(j=1;j<=8;j++)
if(sol[i][j]==0)
sol[i][j]=sol[i-1][j];
fscanf(f,"%ld",&t);
for(i=1;i<=t;i++)
{fscanf(f,"%ld %ld",&p,&k);
fprintf(g,"%ld\n",sol[p][k]);}
fclose(f);
fclose(g);
return 0;}