题目描述

Bajtazar 拥有一套数量庞大的 Bajtemon 卡牌收藏。在他的卡牌堆中，每张卡牌上都画着一只 Bajtemon，并标注了它进化前和进化后的战斗力。Bajtazar 决定卖掉这套收藏。根据《字节-比特卡牌交易协议》，收藏的总价值与卡牌堆中所有 Bajtemon 战斗力的最大公约数成正比。然而，这份协议并未考虑到一张卡牌可能标注多个战斗力的情况，因此 Bajtazar 可以自由选择每张卡牌是使用进化前的战斗力，还是进化后的战斗力。

当然，他希望通过选择使最终的最大公约数尽可能大，从而卖出最高的价格。请你写一个程序，帮助他计算出能卖出的最高价值。

输入格式

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 10^{6})$，表示 Bajtazar 卡牌堆中的卡牌数量。接下来的 $n$ 行描述每张卡牌上的 Bajtemon，每行包含用单个空格分隔的两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i} \leq 5 \cdot 10^{5}, 1 \leq b_{i} < 2^{63})$，分别表示第 $i$ 只 Bajtemon 进化前和进化后的战斗力。注意，进化后的战斗力可能比进化前的小。

输出格式

输出只有一行，包含一个整数，表示 Bajtazar 通过选择战斗力能获得的最大公约数。

4
5 7
10 15
13 20
7 5

5

样例 2

见附加文件下 [kol1.in](file:kol1.in) 和 [kol1.out](file:kol1.out)。

该样例满足 $n=2; a_{1}=18900, b_{1}=22050, a_{2}=14700, b_{2}=17640$，答案是 $7350$；

样例 3

见附加文件下 [kol2.in](file:kol2.in) 和 [kol2.out](file:kol2.out)。

该样例满足 $n=100000; a_{i}=100000+i, b_{i}=100001+i$，答案是 $2$。

数据范围与提示

详细子任务附加限制及分值如下表所示。