#include <cstdio>
#include <cstring>
int main()
{int x,y,z,max,j,n,i,k,t,v[100009],a[8][10009];
 
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 
 a[0][0]=1;a[0][1]=1;
 for (i=1;i<=7;i++) a[i][0]=0;
 memset(v,0,sizeof(v));
 
 a[1][0]=2;a[1][1]=2;a[1][2]=3;
 
 for (i=4;i<=100001;i++)
 {if (i%2==0) v[i]++;
  if (i%3==0) v[i]++;
  if (v[i]==0) for (j=i;j<=1000;j+=i) v[j]++;
  a[v[i]][0]++;a[v[i]][a[v[i]][0]]=i;
 }
 
 scanf("%d",&t);
 for (i=1;i<=t;i++)
 {scanf("%d %d",&n,&k);
  max=0;
	  x=1;y=a[k][0];
	  while (x<=y)
	  {z=(x+y)/2;
	   if (a[k][z]==n) {max=n;x=y+1;} else
		   if (a[k][z]>n) {y=z-1;} else
			   if ((a[k][z]<n)) {x=z+1;if (a[k][z]>max) max=a[k][z];}
			   
	  }
	  printf("%d\n",max);
 }
 /*for (i=0;i<=8;i++)
 {for (j=1;j<=a[i][0];j++)
	 printf("%d ",a[i][j]);
 printf("\n");
 }*/
 return 0;
}