#include <stdio.h>
#define MAXK 7
#define MAXN 1000000
int m[MAXK+1][MAXN], c[MAXN+1];
inline void precalc(){
    int i, j;
    for(i=1; i<=MAXK; i++){
        m[i][++m[i][0]]=0;
    }
    for(i=2; i<=MAXN; i++){
        if(c[i]==0){
            for(j=i; j<=MAXN; j+=i){
                c[j]++;
            }
        }
    }
    for(i=2; i<=MAXN; i++){
        m[c[i]][++m[c[i]][0]]=i;
    }
}
int main(){
    int t, n, k, i, rez, pas;
    FILE *fin, *fout;
    fin=fopen("divprim.in", "r");
    fout=fopen("divprim.out", "w");
    precalc();
    fscanf(fin, "%d", &t);
    for(i=0; i<t; i++){
        fscanf(fin, "%d%d", &n, &k);
        if(k==0){
            fprintf(fout, "1\n");
        }
        rez=0;
        for(pas=1<<20; pas!=0; pas>>=1){
            if((rez+pas<=m[k][0])&&(m[k][rez+pas]<=n)){
                rez+=pas;
            }
        }
        fprintf(fout, "%d\n", m[k][rez]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}