#include<stdio.h>
#define maxn 1000005
int c;
long long  t,n,k,i,j,a[maxn];
FILE *f,*g;
int main()
{a[2]=1;
for(i=2;i<=maxn;i+=2)
a[i]=1;
for(i=1;2*i+1<=maxn;i++)
if(a[2*i+1]==0)
{for(j=2*i+i;j<=maxn;j+=2*i+1)
a[j]++;}
f=fopen("divprim.in","r");
g=fopen("divprim.out","w");
fscanf(f,"%lld",&t);
for(i=1;i<=t;i++)
{c=0;
fscanf(f,"%lld %lld",&n,&k);
for(j=n;j>1&&!c;j--)
 if(a[j]==k)
{fprintf(g,"%lld\n",j);
c=1;}
if(c==0)
fprintf(g,"0\n") ;}
fclose(f);
fclose(g);
return 0;}