// Online C++ compiler to run C++ program online
#include <iostream>
using namespace std;
bool loop(long long k, long long i) {
    for (long long x = 1; x * x <= i && x <= k; x++) {
        if (i % x == 0) {
            long long y = i / x;
            if (y <= k) return false;  
        }
    }
    return true; 
}


void solve() {
    long long n,k;
    cin >> n >> k;
    bool fl = true;
    for(long long i = n; i > k; i--) {
        if(loop(k,i)) {
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
}

int main() {
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}