#include<fstream.h>
#define maxn 1000005
int c;
long long  t,n,k,i,j,a[maxn];
ifstream f("divprim.in");
ofstream g("divprim.out");
int main()
{
for(i=2;i<=maxn;i++)
if(a[i]==0)
{for(j=i+i;j<=maxn;j+=i)
a[j]++;}
f>>t;
for(i=1;i<=t;i++)
{c=0;
f>>n>>k;
for(j=n;j>1&&!c;j--)
 if(a[j]==k)
{g<<j<<endl;
c=1;}
if(c==0)
g<<0<<endl;}
f.close();
g.close();
return 0;}