#include<stdio.h>
#define nrmax 1000001
int max,v[nrmax],mat[8][nrmax];
long int i,j;
void ciur()
{
 for(i=2;i<=1000000;i++)
     if(v[i]==0)
     {
      for(j=i;j<=1000000;j=j+i)
	  {v[j+i]++;}
	  }

 }
void detmax()
{max=0;
 for(int b=j;b>=1;b--)
   if(v[b]==i){max=b;break;}
 }
void caut()
{
 for(i=1;i<=7;i++)
   {
    for(j=1;j<=1000000;j++)
      {detmax();
       mat[i][j]=max;

       }
   }
}


int main()
{
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
      
 ciur();
 caut();
 long int v,k,n;
 scanf("%ld ",&n);

 for(i=1;i<=n;i++)
  {
   scanf("%ld %ld",v,k);
   printf("%ld\n",mat[k][v]);
   }
 return 0;
 }