#include <bits/stdc++.h>
#define NMAX 1000000
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t, n, k, h[8][100006];
int ciur[1000005];
void Ciurulet()
{
    for (int i = 2; i <= NMAX; ++i)
    {
        if (ciur[i] == 0)
        {
            for (int j = i; j <= NMAX; j += i)
            {
                ciur[j]++;
            }
        }
    }
    for (int i = 1; i <= NMAX; ++i)
    {
        h[ciur[i]][++h[ciur[i]][0]] = i;
    }
}

int main()
{
    Ciurulet();
    fin >> t;
    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;
}