#include <fstream>

using namespace std;

const int KMAX = 7;
const int NMAX = 1000000;

int ciur[1 + NMAX];

int dp[1 + NMAX][1 + KMAX];

void initCiur()
{
    for (int i = 2; i <= NMAX; i++)
    {
        if (ciur[i] == 0)
        {
            for (int j = i; j <= NMAX; j = j + i)
            {
                ciur[j]++;
            }
        }
    }
}

void dinamica()
{
    for (int i = 1; i <= NMAX; i++)
    {
        for (int j = 0; j <= 7; j++)
        {
            dp[i][j] = dp[i - 1][j];
        }
        if (ciur[i] <= 7)
        {
            dp[i][ciur[i]] = i;
        }
    }
}

int main()
{
    ifstream in("divprim.in");
    ofstream out("divprim.out");
    int t, n, k;

    initCiur();
    dinamica();

    in >> t;
    for (int i = 1; i <= t; i++)
    {
        in >> n >> k;

        out << dp[n][k] << '\n';
    }

    return 0;
}