#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

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

const int MAXN = 1000005;
int tst;
int v[MAXN];
vector<int> c[10];

int main() {

    c[0].push_back(1);
    for (int i = 2; i < MAXN; ++i) {
        if (v[i] <= 7) {
            if (v[i] == 0) {
                c[1].push_back(i);
            }
            else {
                c[v[i]].push_back(i);
            }
        }
        if (v[i] == 0) {
            for (int j = i + i; j < MAXN; j += i) {
                v[j]++;
            }
        }
    }

    fin >> tst;
    for (int var = 1; var <= tst; ++var) {
        int n, k;
        fin >> n >> k;
        int sol = 0;
        int st = 0;
        int dr = c[k].size() - 1;
        while (st <= dr) {
            int mid = (st + dr) / 2;
            if (c[k][mid] <= n) {
                sol = c[k][mid];
                st = mid + 1;
            }
            else {
                dr = mid - 1;
            }
        }
        fout << sol << '\n';
    }

    fout.close();
    return 0;
}