#include <stdio.h>
#define N 1000001
#define K 8
int count[N],max[K][N];
int main ()
{
	 int i,j,n,k,t;
	 freopen("divprim.in","r",stdin);
	 freopen("divprim.out","w",stdout);
	 
	 for (i=2;i<N;i+=2)
	 {
		 count[i]=1;
	 }
	 for (i=3;i<N;i+=2)
	 {
		 if(count[i]==0)
			 for (j=i;j<N;j+=i)
				 count[j]++;
	 }
	 for (i=1;i<N;i++)
	 {
		 for (j=0;j<K;j++)
		{
		  if(count[i]==j)
			{
		     max[j][i]=i;
		    }
	   else
	   {
		   max[j][i]=max[j][i-1];
	   }
	  }
	 }
	 scanf("%d",&t);
	 for (i=0;i<t;i++)
	 {
		 scanf("%d%d",&n,&k);
		 printf("%d\n",max[k][n]);
	 } 
 return 0;
}