#include<fstream.h>
long t,n,k,sw,s,x,m,d;
ifstream f("divprim.in");
ofstream g("divprim.out");
int main()
{
f>>t;
for (int i=1;i<=t;i++)
{ f>>n>>k;
  int s=0;
  for(int x=n;i>=1;i--)
  {
  for(int j=3;i<=x/2;i+=2)
  if(x%j==0)
  { sw=1;
    d=2;
   while(d<=j/2 &&sw==0)
    {
    if(j%d==0)
     sw=1;
     d++;}


     if(sw==0)
     s++;

     }

     if(s==k)
     {
     g<<x;
     m++;
     }

     }

     if(m==0)
     g<<0;

       }

     f.close();
     g.close();
     return 0;
     }