#include <stdio.h>
#define N 1000001
#define K 8
int count[N],max[K][N];
int main ()
{int i,j,n,k,t;
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 
 for (i=2;i<N;i+=2)
 {count[i]=1;
 }
 for (i=3;i<N;i+=2)
 {if(count[i]==0)
   for (j=i;j<N;j+=i)
    count[j]++;
 }
 for (i=1;i<N;i++)
 {for (j=0;j<K;j++)
  {if(count[i]==j)
   {max[j][i]=i;
   }
   else
   {max[j][i]=max[j][i-1];
   }
  }
 }
 scanf("%d",&t);
 for (i=0;i<t;i++)
 {scanf("%d%d",&n,&k);
  printf("%d\n",max[k][n]);
 }
 
 
 return 0;
}