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

const int KMAX = 7;
const int NMAX = 1e6;

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

vector<int> divprim[KMAX + 1];
int sieve[NMAX + 1];

void compute_sieve() {
    sieve[0] = sieve[1] = 0;
    for (int i = 2; i <= NMAX; i++) {
        if (sieve[i]) continue;
        for (int j = i; j <= NMAX; j += i)
            sieve[j]++;
    }
}
void compute_divprim() {
    compute_sieve();
    for (int k = 1; k <= KMAX; k++) {
        divprim[k].push_back(0);
        for (int i = 1; i <= NMAX; i++)
            if (sieve[i] == k)
                divprim[k].push_back(i);

    }
    // for (auto a : divprim[1])
    //         fout << a << ' ';
    //     fout << '\n';
    //     fout << "---" <<'\n';
}
void solve_case() {
    int n, k; fin >> n >> k;
    auto it = upper_bound(divprim[k].begin(), divprim[k].end(), n);

    if (it != divprim[k].begin())
        --it;

    fout << *it << '\n';}

int main() {
    compute_divprim();
    int t; fin >> t;

    for (; t > 0; t--) {
        solve_case();
    }
    return 0;
}