#include<cstdio>
int div[1000005];
int last[10],num[1000005][8];
int main(){
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
int t,i1,n,i,j,k;
for(i=2;i<=1000000;i++)
if (div[i]==0){
div[i]=1;
for(j=i+i;j<=1000000;j=j+i)
div[j]++;}
for(i=2;i<=1000000;i++){
last[div[i]]=i;
for(j=0;j<=7;j++)
num[i][j]=last[j];}
scanf("%d",&t);
for(i1=1;i1<=t;i1++){
scanf("%d%d",&n,&k);
printf("%d\n",num[n][k]);}
return 0;}