#include <bits/stdc++.h>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
const int DIM = 1e6;
int nrdiv[1000010], mat[1000010][8];

inline void genCiur() {
    for(int i=2; i<=DIM; i++)
        if(!nrdiv[i])
            for(int j=i; j<=DIM; j+=i) nrdiv[j]++;
}

inline void prelucru() {
    for(int j=0; j<=7; j++) {
        for(int i=1; i<=DIM; i++) {
            if(nrdiv[i] == j) mat[i][j] = i;
            else mat[i][j] = mat[i - 1][j];
        }
    }
}

int main()
{
    genCiur();
    prelucru();
    int tt; fin >> tt;
    while(tt--) {
        int x, k; fin >> x >> k;
        fout << mat[x][k] << '\n';
    }

    return 0;
}