//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <numeric>
#include <iterator>
#include <math.h>
#include <set>
#include <functional>
#include <fstream>
#include <chrono>
#include <random>
#include <assert.h>

#define all(x) begin(x), end(x)
#define isz(x) int(size(x))
#define forx(x, n) for(int x = 0; x < n; ++x)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::pair;
using ll = long long;
using ull = unsigned long long;
using real = long double;
using uint = unsigned int;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vvvpii = vector<vvpii>;

const auto ready = []()
{
	cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	return true;
}();

const int MX_N = 50000;
std::bitset<MX_N> is_prime;
vector<int> primes;

void precalc()
{
	is_prime.set();
	is_prime[0] = is_prime[1] = 0;
	for (int i = 2; i < MX_N; ++i)
	{
		if (is_prime[i])
		{
			for (long long j = 1LL * i * i; j < MX_N; j += i)
			{
				is_prime[j] = 0;
			}
		}
	}
	for (int i = 2; i < MX_N; ++i)
	{
		if (is_prime[i])
		{
			primes.push_back(i);
		}
	}
}

int solve(int l, int r)
{
	int ans = -1;

	auto check_prime = [&](int x)
	{
		bool ok = true;
		for (auto &el : primes)
		{
			if (x % el == 0 && x != el) ok = false;
		}
		return ok;
	};

	int p = r - l;
	int last = l;
	while (p >= 2)
	{
		int step = (l + p - 1) / p;
		int first = step * p;
		while(first > last)
		{
			int shift = (first - last + step) / (1 + step);
			last += shift;
			first -= step * shift;
			p -= shift;
			if (first < l)
			{
				first += p;
				++step;
			}
		}
		while (first >= l && !check_prime(p))
		{
			first -= step;
			--p;
			++last;
		}
		if (first >= l && check_prime(p))
		{
			if (p > ans) ans = p;
			break;
		}
	}
	return ans;
}

int naive1(int l, int r)
{
	int ans = -1;

	auto factorize = [&](int x)
	{
		for (auto &el : primes)
		{
			while (x % el == 0)
			{
				ans = std::max(ans, el);
				x /= el;
			}
		}
		if (x > 1) ans = std::max(ans, x);
	};

	for (int i = l; i <= r; ++i)
	{
		for (int j = i + 1; j <= r; ++j)
		{
			int x = std::gcd(i, j);
			factorize(x);
		}
	}
	return ans;
}

int naive2(int l, int r)
{
	std::map<int, int> cnt;
	int ans = -1;
	auto factorize = [&](int x)
	{
		for (auto &el : primes)
		{
			if (x % el == 0)
			{
				++cnt[el];
			}
			while (x % el == 0)
			{
				x /= el;
			}
		}
		if (x > 1) ++cnt[x];
	};

	for (int i = l; i <= r; ++i)
	{
		factorize(i);
	}
	for (auto &el : cnt)
	{
		if (el.second > 1) ans = el.first;
	}
	return ans;
}

int main()
{
	precalc();
	int t;
	cin >> t;
	for(int i = 0; i < t; ++i)
	{
	    int l, r;
	    cin >> l >> r;
	    cout << solve(l, r) << "\n";
	}
	return 0;
}