#include <cstdio>
#include <cstring>
#define NMAX 1000005

int a[8][NMAX];

int main()
{int x,y,z,max,j,n,i,k,t;
 
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 
 for (i=1;i<=7;i++) a[i][0]=0;
 for (i=1;i<NMAX;i++) a[0][i]=0;
 
 a[1][0]=2;a[1][1]=2;a[1][2]=3;
 
 for (i=4;i<NMAX;i++)
 {if (i%2==0) a[0][i]++;
  if (i%3==0) a[0][i]++;
  if (a[0][i]==0) for (j=i;j<NMAX;j+=i) a[0][j]++;
  a[a[0][i]][0]++;a[ a[0][i] ]        [ a[ a[0][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);
 }
 
 return 0;
}