#include <fstream>

using namespace std;

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

int t, n, k, i, j, m;
int ciur[1000001];
bool prim1[1000001];
int prim[1000001][8], mx, pt;

int main()
{
    for (i = 2; i <= 1000000; i++)
        if (prim1[i] == false)
        for (j = i; j <= 1000000; j += i)
            ciur[j]++, prim1[j] = true;

    for (i = 1; i <= 1000000; i++)
    {
        for (j = 1; j <= 7; j++)
            if (ciur[i] == j)
                prim[i][j] = i;
            else
                prim[i][j] = prim[i-1][j];
    }
    f >> t;
    for (i = 1; i <= t; i++)
    {
        f >> n >> k;
        g << prim[n][k]<< "\n";
    }
    return 0;
}