#include    <fstream>

using namespace std;

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

int T, N[100000], K[100000];

bool isPrime(int x)
{
    for (int i = 2; i <= x / 2; i ++)
        if (x % i == 0)
            return false;

    return true;
}

void Read()
{
    fin >> T;

    for (int i = 0; i < T; i ++)
        fin >> N[i] >> K[i];
}

int CountPrimeDiv(int x)
{
    int c = 0;

    for (int i = 2; i <= x / 2; i ++)
        if (x % i == 0 && isPrime(i))
            c ++;

    return c;
}

int Search(int t)
{
    for (int i = N[t]; i >= 4; i --)
        if (!isPrime(i) && CountPrimeDiv(i) == K[t])
            return i;

    return 0;
}

int main()
{
    Read();

    for (int i = 0; i < T; i ++)
        fout << Search(i) << "\n";

    return 0;
}