#include <fstream>

using namespace std;

const int MAX_N = 1e6;
const int MAX_K = 6;
int ciur[MAX_N + 1], nrdiv[MAX_N + 1];
int answer[MAX_N + 1][MAX_K + 1];
int t, n, k;

void precalc() {
    for (int d = 2; d * d <= MAX_N; d++) {
        if (!ciur[d]) {
            for (int i = d * d; i <= MAX_N; i += d) {
                ciur[i] = true;
            }
        }
    }
    for (int i = 2; i <= MAX_N; i++) {
        if (!ciur[i]) {
            for (int j = i; j <= MAX_N; j += i) {
                nrdiv[j]++;
            }
        }
    }
    for (int i = 1; i <= MAX_N; i++) {
        for (int j = 1; j <= MAX_K; j++) {
            if (nrdiv[i] == j) {
                answer[i][j] = i;
            } else {
                answer[i][j] = answer[i - 1][j];
            }
        }
    }
}

int main() {
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    precalc();
    fin >> t;
    while (t--) {
        fin >> n >> k;
        fout << answer[n][k] << "\n";
    }
    return 0;
}