# include <stdio.h>
# include <math.h>
long prim  (long int x)
{
int i;
if (x==0 || x==1)
return 0;
if (x==2)
return 1;
for (i=2;i<=sqrt(x);i++)
if (x%i==0)
return 0;
return 1;
}
long int q,k,l,n,i,p,t,ok,j;
int main ()
{
freopen ("divprim.in","r",stdin);
freopen ("divprim.out","w",stdout);
scanf ("%li",&t);
for (i=0;i<t;i++)
{
ok=0;
scanf ("%li",&n);
scanf ("%li",&k);
p=n;
while (p>0)
{
q=0;
for (l=3;l<=p;l=l+2)
if (p%l==0)
if (prim (l)==1)
q++;
if (p%2==0)
q++;
if (q==k)
{
printf ("%li",p);
printf ("\n");
ok=1;
break;
}
p--;
}
if (ok==0)
{
printf ("0");
printf ("\n");
}
}
return 0;
}