#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t, n, k, h[8][100006];
int main()
{
    fin >> t;
    for (int i = 1; i <= 100000; ++i)
    {
        int contor = 0, x = i;
        for (int j = 2; j * j <= x; ++j)
        {
            if (x % j == 0)
            {
                ++contor;
                while (x % j == 0) x = x / j;
            }
        }
        if (x > 1) ++contor;
        h[contor][++h[contor][0]] = i;
    }
    while (t--)
    {
        fin >> n >> k;
        int st = 1, dr = h[k][0], sol = 0;
        while (st <= dr)
        {
            int mid = (st + dr) / 2;
            if (h[k][mid] <= n)
            {
                sol = h[k][mid];
                st = mid + 1;
            }
            else
            {
                dr = mid - 1;
            }
        }
        fout << sol << "\n";
    }
    return 0;
}