#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(){

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

        if(ciur[i] == 0){
            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 = 5;
    int mij;

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

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

    return mat[poz][st-1];
}
int main(){
    f>>t;

    makeciur();

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

        f>>n>>k;
        g<<cautbin(n,k)<<"\n";
    }


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