#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int T, k, n, d[1000005], fr[8], m[8][379725];

void Constr()
{
    int i, j;
    for(i = 2; i <= 1000000; i++)
        if(d[i] == 0)
            for(j = i; j <= 1000000; j += i)
                d[j]++;
    for(i = 2; i <= 1000000; i++)
        if(d[i] <= 7)
            m[d[i]][++m[d[i]][0]] = i;
}

int main()
{
    int i, j;
    fin >> T;
    Constr();
    /*for(i = 1; i <= 7; i++)
    {
        for(j = 1; j <= 10; j++)
            fout << m[i][j] << " ";
        fout << "\n";
    }
    fout << "\n";
    */
    while(T--)
    {
        fin >> n >> k;
        int st = 1, dr = m[k][0], mij, ans = 0;
        while(st <= dr)
        {
            mij = (st + dr) / 2;
            if(m[k][mij] <= n)
            {
                ans = m[k][mij];
                st = mij + 1;
            }
            else
                dr = mij - 1;
        }
        fout << ans << "\n";
    }
    return 0;
}