B. Ослабленный Общий Делитель
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В процессе исследования свойств наибольшего общего делителя (НОД) набора чисел известный математик Ильдар предложил новую концепцию ослабленного общего делителя (ООД) набора пар чисел.

Для заданного набора пар целых чисел $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, ..., $$$(a_n, b_n)$$$ их ООД называется произвольное число превосходящее $$$1$$$, которое делит хотя бы один элемент в каждой паре. ОДД может и не существовать для некоторых наборов.

Например, если набор пар имеет вид $$$[(12, 15), (25, 18), (10, 24)]$$$, то их ОДД может быть равен $$$2$$$, $$$3$$$, $$$5$$$ или $$$6$$$ (каждое из этих чисел строго больше $$$1$$$ и делит хотя бы одно число в каждой паре).

Вы — аспирант Ильдара, и ваша задача помочь ему с вычислением ООД. Поможете ему с эффективной реализацией вычисления ООД?

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

В первой строке задано число $$$n$$$ ($$$1 \le n \le 150\,000$$$) — количество пар.

В каждой из следующих $$$n$$$ строк задано по два целых числа $$$a_i$$$, $$$b_i$$$ ($$$2 \le a_i, b_i \le 2 \cdot 10^9$$$).

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

Выведите единственное число — ООД списка пар.

Если возможных ответов несколько, выведите любой; если ответа не существует, выведите $$$-1$$$.

Примеры
Входные данные
3
17 18
15 24
12 15
Выходные данные
6
Входные данные
2
10 16
7 17
Выходные данные
-1
Входные данные
5
90 108
45 105
75 40
165 175
33 30
Выходные данные
5
Примечание

В первом примере одним из возможных ООД является число $$$6$$$. В первой паре оно делит $$$18$$$, во второй — $$$24$$$, а в третьей — $$$12$$$.

Во втором примере ни одно число, большее $$$1$$$, не удовлетворяет условию.

В третьем примере одним из возможных ответов является $$$5$$$. Обратите внимание, что одним из возможных ответов также является $$$15$$$, но в задаче не требуется максимизировать ответ.