# include <stdio.h>
short a[1000010];
long int i,j,n,k,t,q;

int main ()
{
freopen ("divprim.in","r",stdin);
freopen ("divprim.out","w",stdout);
scanf ("%li",&t);
for (i=2;i<=500000;i++)
if (a[i]==0)
for (j=i;j<=500000;j=j+i)
a[j]++;



for (q=0;q<t;q++)
{
scanf ("%li",&n);
scanf ("%li",&k);
for (i=n;i>=0;i--)
if (a[i]==k)
{
printf ("%i\n",i);
break;
}
if (i==-1)
printf ("0\n");
}
return 0;
}