Наибольшее общее простое
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наверное, вам хорошо известны понятия наибольшего общего делителя и наименьшего общего кратного. В этой задаче мы не будем просить вас их искать.

Вместо этого рассмотрим наибольшее общее простое двух натуральных чисел $$$\operatorname{gcp}(a, b)$$$ — это такое наибольшее простое число, на которое одновременно делится и $$$a$$$, и $$$b$$$.

Заметим, что не для любой пары чисел определено их наибольшее общее простое. Например, $$$\operatorname{gcp}(10, 15) = 5$$$, a $$$\operatorname{gcp}(2, 3)$$$ не определено.

Вам предстоит ответить на $$$t$$$ запросов, содержащих пару чисел $$$l$$$ и $$$r$$$. Для каждого запроса вам нужно:

- найти наибольшее простое число $$$p$$$ такое, что существуют два числа $$$a$$$ и $$$b$$$ $$$(a \neq b)$$$ на отрезке $$$[l;r]$$$ такие, что $$$\operatorname{gcp}(a, b)=p$$$,
- или сообщить, что такого простого числа $$$p$$$ не существует.

Например, пусть заданы $$$l = 3$$$, $$$r = 10$$$. Тогда $$$p = 5$$$, так как $$$\operatorname{gcp}(5, 10) = 5$$$.

Входные данные

В первой строке входные данных содержится одно целое число $$$t$$$ $$$(1 \leq t \leq 1000)$$$.

Далее следует $$$t$$$ строк, в каждой из которых содержатся два числа $$$l$$$ и $$$r$$$ $$$(1 \leq l \leq r \leq 10^9)$$$ — отрезок запроса.

Выходные данные

Для каждого запроса в отдельной строке выведите ответ:

- наибольшее простое число $$$p$$$, для которого на отрезке $$$[l, r]$$$ существуют два разных числа $$$a$$$ и $$$b$$$ таких, что $$$\operatorname{gcp}(a, b)=p$$$,
- или $$$-1$$$, если такого числа не существует.

Пример

Входные данные

    41 1005000 100500800000000 100000000079 81

Выходные данные

    4750231166666649-1

Примечание

В примере $$$p = 47$$$, так как на отрезке $$$[1, 100]$$$ существуют числа $$$a = 47$$$, $$$b = 94$$$ такие, что $$$\operatorname{gcp}(a, b) = \operatorname{gcp}(47, 94) = 47$$$.