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

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

const int N = 1e6 + 5;

int phi[N], t, n, k;
vector <int> div[8];

int main() {
    for (int i = 2; i < N; i += 2)
        phi[i]++;
    for (int i = 3; i < N; i += 2)
        if (!phi[i])
            for (int j = i; j < N; j += i)
                phi[j]++;
    for (int p = 2; p < N; ++p)
        div[phi[p]].push_back (p);
    fin >> t;
    while (t--) {
        fin >> n >> k;
        int step = 1 << 16, sol = 0;
        for (; step; step >>= 1)
            if (sol + step < div[k].size() && div[k][sol + step] <= n)
                sol += step;
        if (div[k][sol] > n)
            fout << "0\n";
        else
            fout << div[k][sol] << "\n";
    }
}