#include <iostream>
#include <fstream>

//#define int long long

using namespace std;

int divizori[1000000+1];

signed main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    for (int i=2; i<=1000000; i++) {
        if (divizori[i]==0) {
            for (int j=i; j<=1000000; j+=i) {
                divizori[j]++;
            }
        }
    }

    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        int x, div;
        cin >> x >> div;
        while (divizori[x]!=div && x>0) {
            x--;
        }
        cout << x << "\n";
    }
    return 0;
}