#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ull unsigned long long

using namespace std;

const int SIEVE_INF = 10000000;

vector <int> sieve_prime(SIEVE_INF + 1, 1);

bool is_prime(int x)
{
    if (x <= SIEVE_INF)
        return sieve_prime[x];

    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return 0;

    return 1;
}

int prev_prime(int upper_border)
{
    while (!is_prime(upper_border))
        upper_border--;

    return upper_border;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int test;
    cin >> test;

    for (int i = 2; i <= SIEVE_INF; i++)
    {
        if (!sieve_prime[i])
            continue;

        if (i > SIEVE_INF / i)
            continue;

        for (int j = i * i; j <= SIEVE_INF; j += i)
            sieve_prime[j] = 0;
    }

    while (test--)
    {
        int l, r;
        cin >> l >> r;

        int ans = -1;

        for (int z = 1; z * z <= r; z++)
        {
            int upper_border = r / z;

            if (upper_border < 2)
                continue;

            int prime = prev_prime(upper_border);

            if (z * prime - prime >= l)
            {
                ans = max(ans, prime);
                break;
            }
        }

        for (int prime = 2; prime * prime <= r; prime++)
        {
            if (!sieve_prime[prime])
                continue;

            int z = r / prime;

            if (prime * z - prime >= l)
                ans = max(ans, prime);
        }

        cout << ans << "\n";
    }
}
