#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];
int p;

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 = mat[poz][0];
    int mij;

    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);

        if(mat[k][poz] > n)
            g<<0<<"\n";
        else
            g<<mat[k][poz]<<"\n";
    }


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