#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");

const int N = 1000005;

int t,n,k;
int ciur[N];
int mat[7][N];

void makeciur(){

    for(int i =1; i<= 7; i++){
        mat[i][0] = 1;
        mat[i][1] = 0;
    }
    for(int i = 2; i < N-3; i++){

        if(ciur[i] == 0){

            mat[1][0]++;
            int nr = mat[1][0];
            mat[1][nr] = i;

            for(int j = 2; j*i < N-3; j++){
                ciur[i*j] = ciur[i*j] + 1;
            }
        }

        if(ciur[i] > 0 && ciur[i] <=7){

            mat[ciur[i]][0]++;
            int nr = mat[ciur[i]][0];
            mat[ciur[i]][nr] = i;
            //g<<ciur[i]<<" "<<i<<"\n";
        }
    }
}

int cautbin(int num,int poz){

    int st = 1;
    int dr = mat[poz][0];
    int mij;
    int p = 0;

    while(st<=dr){
        mij = (st+dr)/2;

        if(mat[poz][mij]>num)
            dr = mij -1;
        else if(mat[poz][mij]<num){
            st = mij +1;
            p = mij;
        }
        else{
            return mij;
        }
    }

    return p;
}
int main(){
    f>>t;

    makeciur();

    for(int i =1; i<= t; i++){

        f>>n>>k;
        int poz = cautbin(n,k);

        g<<mat[k][poz]<<"\n";
    }


    f.close();
    g.close();
    return 0;
}