#include<stdio.h>

const long int MAX=1000000;

int div[10000002];

long int i,j,K,x,T,N,mark,v[7]={2,6,30,210,2310,30030,510510};


int main()
{

FILE*in=fopen("divprim.in","r");
FILE*out=fopen("divprim.out","w");


fscanf(in,"%ld",&T);
div[1]=1;

for(i=2;i<=MAX/2;++i)
 div[2*i]=1;

for(i=3;i<=MAX;i=i+2)
 {
  if(div[i]==0)
   {
    for(j=2;j<=MAX/i;++j)
     div[j*i]+=1;
   }
 }
/*
for(i=1;i<=1000;i++)
 fprintf(out,"%d\n",div[i]);
*/

for(i=1;i<=T;++i)
{
 fscanf(in,"%ld %ld",&N,&K);
 if(K==0) fprintf(out,"0\n");
{
 if(N<v[K-1]) fprintf(out,"0\n");
  else
{

 mark=N;
 while(mark>=1)
 {
  if(div[mark]==K||K==1&&div[mark]==0) break;
  --mark;
 }
 fprintf(out,"%d\n",mark);
}
}
}
fcloseall();
return 0;
}