#include <fstream>

using namespace std;

ifstream cin("divprim.in"); ofstream cout("divprim.out");

const int NMAX = 1e6;
int t, n, k, p[NMAX + 10], a[NMAX + 10][8];

void ciur()
{
    for (int i = 2; i <= NMAX; i = i + 2)
        p[i] = 1;
    for (int i = 3; i <= NMAX / 2; i = i + 2)
    {
        if (p[i] == 0)
        {
            for (int j = i + i; j <= NMAX; j = j + i)
                p[j]++;
            p[i] = 1;
        }
    }
}
int main()
{
    ciur();
    for (int i = 1; i <= NMAX; ++i)
        for (int j = 0; j <= 7; ++j)
            if (p[i] == j)
                a[i][j] = i;
            else
                a[i][j] = a[i - 1][j];
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cout << a[n][k] << '\n';
    }
    return 0;
}