著名数学家伊尔达尔在研究一组数的最大公约数(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$$$ 也是允许的,但没有必要最大化输出。