#include <bits/stdc++.h>
#define NMAX 1000
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t, n, k, h[8][100006];
bitset <NMAX + 5> ciur;
int prim[NMAX], z;
void Ciurulet()
{
    ciur[0] = ciur[1] = 1;
    for (int i = 2; i * i <= NMAX; ++i)
    {
        for (int j = i + i; j <= NMAX; j += i)
        {
            ciur[j] = 1;
        }
    }
    prim[++z] = 2;
    for (int i = 3; i <= NMAX; i += 2)
    {
        if (ciur[i] == 0)
        {
            prim[++z] = i;
        }
    }
}
int main()
{
    Ciurulet();
    fin >> t;
    for (int i = 1; i <= 1000000; ++i)
    {
        int contor = 0, x = i;
        for (int j = 1; prim[j] * prim[j] <= x && j <= z; ++j)
        {
            if (x % prim[j] == 0)
            {
                ++contor;
                while (x % prim[j] == 0) x = x / prim[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;
}