#include <fstream>
#include <algorithm>

using namespace std;

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

short ciur[1000001];
int a[1000001][8];

int main()
{
    int T, N, K, i, j;

    ciur[1] = 0;
    for (i = 2; i <= 1000000; ++i)
        if (ciur[i] == 0)
            for (j = i; j <= 1000000; j += i)
                ciur[j]++;
    for (i = 1; i <= 1000000; ++i)
    {
        for (j = 0; j <= 7; ++j)
            a[i][j] = a[i - 1][j];
        a[i][ciur[i]] = i;
    }
    in >> T;
    while (T--)
    {
        in >> N >> K;
        out << a[N][K] << '\n';
    }
    in.close();
    out.close();
    return 0;
}