#include<fstream.h>
#include<math.h>
unsigned t,k,n,r=0,ok,i,j,h,prim,e,l;
int main()
{ifstream f("divprim.in");
ofstream g("divprim.out");
f>>t;i=1;
while(i<=t)
{f>>n;f>>k;ok=0;
for(j=n;j>=1&&ok==0;j--)
  {r=0;
  for(h=2;h<=j;h++)
      if(j%h==0)
       {prim=1;
	for(l=2;l<=sqrt(h);l++)
	  if(h%l==0)
	    prim=0;
	if(prim==1)
	  r++;
       }
  if(r==k)
   {ok=1;e=j;}
  if((j==1)&&(ok==0))
   e=0;
  }
g<<e<<'\n';
i++;
}
f.close();
g.close();
return 0;
}