#include<stdio.h>

char prim[1000001];

int main()
{
 int n,t,k,i,j,ok;
 FILE *f=fopen("divprim.in","r");
 FILE *g=fopen("divprim.out","w");

 fscanf(f,"%d",&t);
 
 prim[0]=0;
 prim[1]=0;
 
 i=2;
 while(i<=1000000)
    {
    if(prim[i]==0) 
	 for(j=i;j<=1000000;j=j+i)
        prim[j]++;
     i++;
   }
 for(i=1;i<=t;i++)
 {
  fscanf(f,"%d%d",&n,&k);
  ok=0;
  while(n>=1)
  { 
   if(prim[n]==k)
   {
	fprintf(g,"%d\n",n);
	ok=1;
    n=0;
   }
   else
   n--;
  }
  if(ok==0)
	fprintf(g,"0\n");
 }
}