#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("divprim.in");
ofstream g ("divprim.out");

const int KMAX = 7 + 1, NMAX = 1000000 + 1;
int n;
int d[NMAX], sol[NMAX][KMAX];

void rezolva () {
    for (int i = 2; i <= NMAX; i++) {
        if (d[i] == 0)
            for (int j = i + i; j <= NMAX; j += i) d[j]++;
        for (int j = 1; j < KMAX; j++) sol[i][j] = sol[i - 1][j];
        if (d[i] < KMAX) sol[i][d[i]] = i;
    }
}

int main () {
    rezolva ();
    f >> n;
    int a, b;
    for (int i = 1; i <= n; i++)
        f >> a >> b,
        g << sol[a][b] << '\n';
    return 0;
}