#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 div[NMAX], sol[NMAX][KMAX];

void rezolva () {
    for (int i = 2; i <= NMAX; i++) {
        if (div[i] == 0)
            for (int j = i + i; j <= NMAX; j += i) div[j]++;
        for (int j = 1; j < KMAX; j++) sol[i][j] = sol[i - 1][j];
        if (div[i] < KMAX) sol[i][div[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;
}