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

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

int t, maxim = -1;
int DivPrim[1000005];
pair<int, int> ts[100005];
vector<vector<int>> kDiv;

void Ciur()
{
    DivPrim[0] = 0;
    DivPrim[1] = 0;

    for (int i = 2; i <= maxim; ++i)
        if (DivPrim[i] == 0)
        {
            ++DivPrim[i];
            for (int j = 2*i; j <= maxim; j += i)
                ++DivPrim[j];
        }
}

int main()
{
    fin >> t;
    for (int i = 0; i < t; ++i)
    {
        fin >> ts[i].first >> ts[i].second;
        maxim = max(maxim, ts[i].first);
    }

    Ciur();

    for (int i = 0; i < 8; ++i)
        kDiv.push_back({});

    for (int i = 1; i <= maxim; ++i)
        kDiv[DivPrim[i]].push_back(i);

    for (int i = 0; i < t; ++i)
    {
        int n = ts[i].first;
        int k = ts[i].second;

        int ind = upper_bound(kDiv[k].begin(), kDiv[k].end(), n) - kDiv[k].begin();
        --ind;
        if (ind < 0 || ind >= kDiv[k].size())
            fout << 0 << '\n';
        else
            fout << kDiv[k][ind] << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}