# include <stdio.h>
char a[1010];
long int i,j,n,k,t,q,b[10];
int main ()
{
freopen ("divprim.in","r",stdin);
freopen ("divprim.out","w",stdout);
scanf ("%li",&t);
for (i=2;i<=1000;i=i+2)
a[i]++;
for (i=3;i<=1000;i=i+2)
if (a[i]==0)
for (j=i;j<=1000;j=j+i)
a[j]++;
b[1]=2;
b[2]=6;
b[3]=30;
b[4]=210;
b[5]=2310;
b[6]=30030;
b[7]=510510;
for (q=0;q<t;q++)
{
scanf ("%li",&n);
scanf ("%li",&k);
i=-1;
if (n>=b[k])
{
for (i=n;i>=b[k];i--)
if (a[i]==k)
{
printf ("%i\n",i);
break;
}
}
else
{
if (i==-1)
printf ("0\n");
}
}
return 0;
}