#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");
int T, N, K, V[1000010];
vector < int > A[10];

void Ciur()
{
    for (int i = 2; i <= 1000000; i++)
    {
        if (!V[i])
        {
            for (int j = i; j <= 1000000; j += i)
            {
                V[j] += 1;
            }
        }
    }
    for (int i = 0; i <= 7; i++) A[i].push_back(0);
    for (int i = 1; i <= 1000000; i++)
    {
        if (V[i] <= 7) A[V[i]].push_back(i);
    }
}

int Caut_Binar(int val, int k)
{
    int st = 0, dr = A[k].size() - 1, mij;
    while (st < dr)
    {
        mij = (st + dr) / 2;
        if (val < A[k][mij]) dr = mij - 1;
        else st = mij + 1;
    }
    mij = (st + dr) / 2;
    if (A[k][mij] > N) mij--;
    return A[k][mij];
}

int main()
{
    Ciur();
    fin >> T;
    while (T--)
    {
        fin >> N >> K;
        if (A[K].size()) fout << Caut_Binar(N, K) << '\n';
        else fout << "0\n";
    }

    fout.close();
    return 0;
}