#include<stdio.h>
#define nrmax 10000
int max,v[nrmax],mat[8][nrmax];
long int i,j;
void ciur()
{
 for(i=2;i<=nrmax-1;i++)
     if(v[i]==0)
     {
      for(j=i;j<=nrmax-1;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<=nrmax-1;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("%d\n",mat[k][v]);
   }
 return 0;
 }