#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl cout << "\n"
#define io ios_base::sync_with_stdio(false); cin.tie(nullptr);

vector<bool> is_prime;

void sieve(int limit = 1000000) {
    is_prime.assign(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i * i <= limit; i++) {
        if (is_prime[i]) {
            for (ll j = i * i; j <= limit; j += i)
                is_prime[j] = false;
        }
    }
}

// Fastest way to find largest prime factor of a number <= 1e9
int largestPF(ll n) {
    if (n <= 1) return 0;
    int maxP = -1;

    // Handle 2
    while (n % 2 == 0) {
        maxP = 2;
        n /= 2;
    }

    // Odd factors
    for (ll i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            maxP = i;
            n /= i;
        }
    }
    if (n > 1) maxP = n;

    return maxP;
}

int main() {
    io;
    sieve();

    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;

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

        bool found = false;
        // Genius part: only check last 10000 numbers (more than enough)
        for (ll x = n; x >= max(2LL, n - 20000); x--) {  // 20k bhi chalega, safe side
            if (largestPF(x) > k) {
                cout << x << "\n";
                found = true;
                break;
            }
        }

        if (!found) {
            cout << -1 << "\n";
        }
    }
    return 0;
}