#include <iostream.h>
#include <fstream.h>
int main()
{
ifstream f("divprim.in");
ofstream g("divprim.out");
int t,i,n[100000],k[100000],d,prim,j,nr,div[100000],y;
f>>t;
for (i=0;i<t;i++)
    f>>n[i]>>k[i];
f.close();
for (i=0;i<t;i++)
    {
     for (d=n[i];d>=n[i]/2;d--)
         {
         nr=0;
         for (y=2;y<=d/2;y++)
             if (d%y==0)
                {
                prim=1;
                for (j=2;j<y/2;j++)
                    if (y%j==0) prim=0;
                if (prim) nr++;   
                }     
         if (nr==k[i]) div[i]=d;
         }
     }
for (i=0;i<t;i++)
    g<<div[i]<<endl;
g.close();
return 0;
}