题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Kolekcjoner Bajtemonów 2

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 通过选择战斗力能获得的最大公约数。

样例 1

输入

4
5 7
10 15
13 20
7 5

输出

5

解释
如果 Bajtazar 选择第三张和第四张卡牌使用进化后的战斗力，而第一张和第二张使用进化前的战斗力，那么最终的战斗力分别是 $5$, $10$, $20$, $5$，它们的最大公约数是 $5$。

样例 2

见附加文件下 kol1.in 和 kol1.out。

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

样例 3

见附加文件下 kol2.in 和 kol2.out。

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

数据范围与提示

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