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

#define ll long long
#define fast ios::sync_with_stdio(false); cin.tie(nullptr);

vector<int> primes;

// Sieve up to 1e6+10 is enough for trial division
void sieve() {
    const int MAXP = 1000010;
    vector<bool> is_prime(MAXP, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAXP; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAXP; j += i)
                is_prime[j] = false;
        }
    }
    for (int i = 2; i < MAXP; i++)
        if (is_prime[i]) primes.push_back(i);
}

int largest_prime_factor(int n) {
    if (n <= 1) return 0; // important: 1 has no prime factors

    int max_prime = -1;

    // Divide by 2
    while (n % 2 == 0) {
        max_prime = 2;
        n /= 2;
    }

    // Odd factors
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            max_prime = i;
            n /= i;
        }
    }

    if (n > 1) max_prime = n;

    return max_prime;
}

void solve() {
    int n, k;
    cin >> n >> k;

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

    // Start from n downto 2 (1 is invalid)
    for (int i = n; i >= 2; i--) {
        int lpf = largest_prime_factor(i);
        if (lpf > k) {
            cout << i << "\n";
            return;
        }
    }

    cout << "-1\n";
}

int main() {
    fast
    sieve(); // precompute small primes (optional, but we don't even need primes list now)

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}