#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int NMax = 1e6 + 5;
const int L = 8;

int ciur[NMax], ans[NMax][L];

void eratos(){
    for(int i = 2; i < NMax; i += 2){
        ciur[i] = 1;
    }
    for(int i = 3; i < NMax; i += 2){
        if(!ciur[i]){
            ciur[i] = 1;
            for(int j = i * 2; j < NMax; j += i){
                ciur[j]++;
            }
        }
    }
}

void precalc(){
    eratos();
    for(int i = 1; i < NMax; i++){
        for(int j = 0; j < L; j++){
            ans[i][j] = ans[i - 1][j];
            ans[i][ciur[i]] = i;
        }
    }
}

int main(){
    int t, x, k;
    fin >> t;
    precalc();
    while(t--){
        fin >> x >> k;
        fout << ans[x][k] << "\n";
    }
    return 0;
}