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

const int NMAX = 1000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    if(!fin.is_open() || !fout.is_open()) return 0;

    vector<int> cntPrimeDiv(NMAX + 1, 0);
    for (int p = 2; p <= NMAX; ++p) {
        if (cntPrimeDiv[p] == 0) {
            for (int j = p; j <= NMAX; j += p) {
                cntPrimeDiv[j] += 1;
            }
        }
    }

    const int KMAX = 7;
    vector<int> vv[KMAX + 1];
    for (int n = 1; n <= NMAX; ++n) {
        int k = cntPrimeDiv[n];
        if (k >= 0 && k <= KMAX) vv[k].push_back(n);
    }

    int t;
    fin >> t;
    for (int i = 0; i < t; ++i) {
        int maxi, div;
        fin >> maxi >> div;
        if (div < 0 || div > KMAX) {
            fout << 0 << '\n';
            continue;
        }
        auto &vec = vv[div];
        if (vec.empty()) {
            fout << 0 << '\n';
            continue;
        }
        auto it = upper_bound(vec.begin(), vec.end(), maxi);
        if (it == vec.begin()) fout << 0 << '\n';
        else {
            --it;
            fout << *it << '\n';
        }
    }

    return 0;
}