#include <bits/stdc++.h>
using namespace std;
ifstream fcin("divprim.in");
ofstream fcout("divprim.out");

const int N = 1e6 + 5;
bool p[N];
int c[N];
vector<vector<int>> v(10);
int t, n, k;

void ciur()
{
    p[2] = 1;
    for (int i = 3; i < N; i += 2)
        p[i] = 1;
    for (int i = 1; i * i < N; i += 2)
        if (p[i])
            for (int j = i * i; j < N; j += 2 * i)
                p[j] = 0;
    for (int i = 1; i < N; i++)
        if (p[i])
            for (int j = i; j < N; j += i)
                c[j]++;
    for (int i = 1; i < N; i++)
        v[c[i]].push_back(i);
}

int main()
{
    ciur();
    fcin >> t;
    while (t--)
    {
        fcin >> n >> k;
        int rasp = 0;
        auto it = upper_bound(v[k].begin(), v[k].end(), n);
        if (it != v[k].begin())
        {
            it--;
            rasp = *it;
        }
        fcout << rasp << '\n';
    }

    return 0;
}