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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;

        if (n == k) {
            cout << "-1\n";
            continue;
        }

        // Start from n and go down
        ll curr = n;
        while (true) {
            if (curr == k) {
                cout << "-1\n";
                break;
            }

            bool good = true;
            // Check if curr has any small factor <= k
            for (ll i = 2; i * i <= curr; i++) {
                if (curr % i == 0) {
                    // Found a small factor ? not good
                    good = false;
                    break;
                }
            }

            if (good) {
                // curr is either prime or has large prime factor (> sqrt(curr) > k possibly)
                // But we need largest prime factor > k
                // So better: just compute largest prime factor directly
                ll lpf = 0;
                ll x = curr;
                while (x % 2 == 0) { lpf = 2; x /= 2; }
                for (ll i = 3; i * i <= x; i += 2) {
                    while (x % i == 0) { lpf = i; x /= i; }
                }
                if (x > 1) lpf = x;

                if (lpf > k) {
                    cout << curr << "\n";
                    break;
                }
            }
            curr--;
        }
    }
    return 0;
}