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