#include <fstream.h>
ifstream f ("divprim.in");
ofstream g ("divprim.out");

int k;
long t,n;

int prim (int x)
{for (int v=2;v<=x/2;v++)
  if (x%v==0) return 0;
return 1;
}

long div()
{f>>n>>k;
for (int h=n;h>=2;h--)
{
long d=0;
for (int j=2;j<=h/2;j++)
  if (h%j==0)
    if (prim(j)==1) d++;
if (d==k) return h;
}
return 0;
}

int main()
{f>>t;
for (int i=0;i<t;i++)
  g<<div()<<endl;
return 1;
}