#include<fstream.h>
#include<math.h>
long t,n,k,i,j,gasit;
long prim(long x)
{
  long i;
   for(i=2;i<=sqrt(x);i++)
    if(x%i==0)
     return 0;
  return 1;
}
long nrdiv(long x)
{
  long nr=0,i;
   for(i=2;i<=n;i++)
    if(x%i==0&&prim(i))
     nr++;
   return nr;
}
int main()
{
  ifstream f("divprim.in");
  ofstream g("divprim.out");
   f>>t;
    for(i=1;i<=t;i++)
     {
      f>>n>>k;
      gasit=0;
       for(j=n;j>=1;j--)
	if(nrdiv(j)==k)
	{
	 g<<j<<"\n";
	 gasit=1;
	 break;
	}
       if(gasit==0)
	g<<"0"<<"\n";
     }
 return 0;
}