#include<fstream.h>

int t,n,k,j,l,d,e,i;

int prim(int);

int main()
{  ifstream fin("divprim.in");
   ofstream fout("divprim.out");
   fin>>t;
   for(i=1;i<=t;i++)
   {  fin>>n>>k;
      for(j=n;j>=0;j--)
      {	e=0;
	for(l=1;l<=j/2;l++)
		if(j%l==0&&prim(l))    e++;
	if(e==k){  fout<<j<<"\n";
		   break;
		}

      }
      if(e==0) fout<<0<<"\n";
   }
   fin.close();
   fout.close();
   return 0;
}

int prim(int a)
{  if(a==1) return 0;
   if(a==2||a==3) return 1;
   if(a%2==0) return 0;
   for(d=3;d*d<a;d+=2)
	if(a%d==0) return 0;
   return 1;
}