#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];

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 < t; ++i)
    {
        int n = ts[i].first;
        int k = ts[i].second;

        int rez = 0;
        for (int j = n; j >= 1; j--)
            if (DivPrim[j] == k)
            {
                rez = j;
                break;
            }
        fout << rez << '\n';
    }

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