← 返回题目列表

Codeforces · 1025/B

B. 弱公约数

中文机器翻译题面 查看原题

著名数学家伊尔达尔在研究一组数的最大公约数(GCD)性质时,引入了整数对列表的弱公约数(WCD)的全新概念。

对于给定的整数对列表 $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, ..., $$$(a_n, b_n)$$$,它们的 WCD 是大于 $$$1$$$ 的任意整数,这样它就能除掉每对中的至少一个元素。对于某些列表,WCD 可能不存在。

例如,如果列表看起来像 $$$[(12, 15), (25, 18), (10, 24)]$$$,那么它们的 WCD 可以等于 $$$2$$$、$$$3$$$、$$$5$$$ 或 $$$6$$$(这些数字中的每一个都严格大于 $$$1$$$ 并除以至少一个数字每对)。

您目前正在 Ildar 的指导下攻读博士学位,这就是为什么这个问题被委托给您。您的任务是有效计算 WCD。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 150\,000$$$) — 对的数量。

接下来的 $$$n$$$ 行包含两个整数值 $$$a_i$$$、$$$b_i$$$ ($$$2 \le a_i, b_i \le 2 \cdot 10^9$$$)。

输出

打印单个整数——这组对的 WCD。

如果有多个可能的答案,则输出任意一个;如果没有答案,则打印 $$$-1$$$。

示例

输入 #1

3
17 18
15 24
12 15

输出 #1

6

输入 #2

2
10 16
7 17

输出 #2

-1

输入 #3

5
90 108
45 105
75 40
165 175
33 30

输出 #3

5

注意

在第一个示例中,答案是 $$$6$$$,因为它将第一对中的 $$$18$$$ 分开,第二对中的 $$$24$$$ 和第三对中的 $$$12$$$ 分开。请注意,其他有效答案也将被接受。

在第二个示例中,没有大于 $$$1$$$ 的整数满足条件。

在第三个示例中,可能的答案之一是 $$$5$$$。请注意,例如 $$$15$$$ 也是允许的,但没有必要最大化输出。