Наверное, вам хорошо известны понятия наибольшего общего делителя и наименьшего общего кратного. В этой задаче мы не будем просить вас их искать.
Вместо этого рассмотрим наибольшее общее простое двух натуральных чисел $$$\operatorname{gcp}(a, b)$$$ — это такое наибольшее простое число, на которое одновременно делится и $$$a$$$, и $$$b$$$.
Заметим, что не для любой пары чисел определено их наибольшее общее простое. Например, $$$\operatorname{gcp}(10, 15) = 5$$$, a $$$\operatorname{gcp}(2, 3)$$$ не определено.
Вам предстоит ответить на $$$t$$$ запросов, содержащих пару чисел $$$l$$$ и $$$r$$$. Для каждого запроса вам нужно:
Например, пусть заданы $$$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)$$$ — отрезок запроса.
Для каждого запроса в отдельной строке выведите ответ:
41 1005000 100500800000000 100000000079 81
4750231166666649-1
В примере $$$p = 47$$$, так как на отрезке $$$[1, 100]$$$ существуют числа $$$a = 47$$$, $$$b = 94$$$ такие, что $$$\operatorname{gcp}(a, b) = \operatorname{gcp}(47, 94) = 47$$$.
