#include<cstdio>
int t,n,k,i,j,v[1001000],x[10][1001000];
FILE *f,*g;
int main(){
    f=fopen("divprim.in","r");
    g=fopen("divprim.out","w");
    for(i=2;i<=1000000;i++){
        if( v[i] == 0 ){
            for(j=i+i;j<=1000000;j+=i){
                v[j]++;
            }
        }
    }
    for(i=0;i<=7;i++){
        for(j=1;j<=1000000;j++){
            if( v[j] == i )
                x[i][j] = j;
            else
                x[i][j] = x[i][ j - 1 ];
        }
    }
    fscanf(f,"%d",&t);
    while(t--){
        fscanf(f,"%d%d",&n,&k);
        fprintf(g,"%d\n",x[k][n]);
    }




    fclose(f);
    fclose(g);
    return 0;
}