Bajtazar 拥有一大批 Bajtemon 卡片。每张卡片上都画着一个 Bajtemon，并标注了它进化前和进化后的战力。Bajtazar 决定出售他的收藏。根据《Bajtocko-Bitocki 关于 Bajtemon 卡片交易的协议》，收藏的价值与卡组中所有 Bajtemon 战力的最大公约数（NWD）成正比。然而，该协议并未预见到存在标注了不止一种战力的卡片，因此对于每张卡片，Bajtazar 可以选择使用其进化前或进化后的战力。

他当然希望选择一种方案，使得最终得到的 NWD 最大。请编写一个程序，帮助他确定出售收藏所能获得的最大价格（即最大 NWD）。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示 Bajtazar 收藏中的卡片数量。 接下来的 $n$ 行包含 Bajtemon 的描述；第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le 5 \cdot 10^5, 1 \le b_i < 2^{63}$)，分别表示第 $i$ 个 Bajtemon 进化前和进化后的战力。进化后的战力可能小于进化前的战力。

输出格式

输出一行一个整数，表示 Bajtazar 可以获得的最大 NWD。

样例

输入 1

4
5 7
10 15
13 20
7 5

输出 1

5

说明 1

如果 Bajtazar 选择第三个和第四个 Bajtemon 进化后的战力，以及第一个和第二个 Bajtemon 进化前的战力，那么这些 Bajtemon 的战力分别为 5, 10, 20 和 5，它们的 NWD 为 5。

子任务

测试集分为以下子任务。每个子任务的测试由一个或多个独立的测试组组成。