#include <bits/stdc++.h>
#define NMAX 1000
using namespace std;

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

bitset <NMAX + 5> ciur;
int prim[NMAX], z, t, n, k;

vector <int> h[8]; // un fel de hash :)

void Ciurulet()
{
    ciur[0] = ciur[1] = 1;
    for (int i = 2; i * i <= NMAX; ++i)
    {
        for (int j = i + i; j <= NMAX; j += i)
        {
            ciur[j] = 1;
        }
    }
    prim[++z] = 2;
    for (int i = 3; i <= NMAX; i += 2)
    {
        if (ciur[i] == 0)
        {
            prim[++z] = i;
        }
    }
}

int descompune(int x)
{
    int contor = 0;
    for (int i = 1; i <= z && prim[i] * prim[i] <= x; ++i)
    {
        if (x % prim[i] == 0)
        {
            ++contor;
            while (x % prim[i] == 0) x = x / prim[i];
        }
    }
    if (x > 1) ++contor;
    return contor;
}

int main()
{
    Ciurulet();
    for (int i = 1; i <= NMAX; ++i)
    {
        int nr = descompune(i);
        h[nr].push_back(i);
    }
    fin >> t;
    while (t--)
    {
        fin >> n >> k;
        int sol = 0, st = 0, dr = h[k].size() - 1;
        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;
}