#include<stdio.h>


int T,i,ok,n,k,j,j2,g;
int m[1000005][8],v[1000005];

int main(){

FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");

fscanf(f,"%d",&T);

   for(i=2;i<=1000000;i++){
     if(v[i]==0){

       for(j=i;j<=1000000;j+=i){
       v[j]++;
       }

     }

   }


    for(i=2;i<=1000000;i++){

       for(j=1;j<=7;j++){
       m[i][j]=m[i-1][j];
       }

     if(v[i]!=m[i][v[i]])m[i][v[i]]=i;

    }


 for(i=1;i<=T;i++){
 fscanf(f,"%d %d",&n,&k);
 fprintf(g,"%d\n",m[n][k]);
 }

fclose(f);
fclose(g);

return 0;
}