#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t, n, k, ciur[1000006];
vector <int> h[8];
int main()
{
    for (int i = 2; i <= 1000000; ++i)
    {
        if (ciur[i] == 0)
        {
            for (int j = i; j <= 1000000; j += i)
            {
                ciur[j]++;
            }
        }
    }
    for (int i = 1; i <= 1000000; ++i) h[ciur[i]].push_back(i);
    fin >> t;
    while (t--)
    {
        fin >> n >> k;
        int st = 0, dr = h[k].size() - 1, 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";
    }
}