#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1'000'000;

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

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    vector<int> cnt(NMAX + 1, 0);
    vector<array<int, 8>> best(NMAX + 1);

    for (int p = 2; p <= NMAX; p++)
        if (cnt[p] == 0)
            for (int multiple = p; multiple <= NMAX; multiple += p)
                cnt[multiple]++;

    for (int k = 0; k <= 7; k++)
        best[0][k] = 0;

    for (int i = 1; i <= NMAX; i++) {
        for (int k = 0; k <= 7; k++)
            best[i][k] = best[i - 1][k];
        int k = cnt[i];
        if (k <= 7)
            best[i][k] = i;
    }

    int T;
    fin >> T;
    while (T--) {
        int N, K;
        fin >> N >> K;
        fout << best[N][K] << "\n";
    }

    return 0;
}