问题文

有 $N$ 组整数对。第 $i$ 组整数对为 $(A_i, B_i)$。

小顾正打算从每对中选择恰好一个整数。选择的 $N$ 个整数的最大公约数最大可以是多少？

约束条件

输入满足以下条件。

• $1 \leq N \leq$$\ 5 \times 10^4$
• $1 \leq A_i,B_i \leq 10^9$
• 输入的值均为整数

输入

从标准输入中按以下格式给出输入。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_N$ $B_N$

输出

输出小顾选择的 $N$ 个整数的最大公约数的最大值。

输入例子 1

2
15 12
18 18

输出例子 1

6

从每对中选择 $12, 18$，最大公约数为 $6$，这是最大的值。

输入例子 2

3
999999929 999999883
999999757 999999929
999999883 999999757

输出例子 2

1