最大公约数的最小公倍数

时间限制：4s
空间限制：1024MB

题目描述

有一个红袋、一个蓝袋和 $N$ 个卡包。第 $i$ 个卡包中有两张卡片，分别写着整数 $a_i,b_i$。对于每个卡包，必须把一张卡片放进红袋，另一张放进蓝袋。

设红袋中所有整数的最大公约数为 $X$，蓝袋中所有整数的最大公约数为 $Y$，得分为 $\operatorname{lcm}(X,Y)$。求可能得到的最大得分。

输入格式

第一行输入整数 $N$，接下来 $N$ 行每行输入两个整数 $a_i,b_i$。

输出格式

输出一个整数，表示最大得分。

样例输入 1

2
2 15
10 6

样例输出 1

10

样例输入 2

5
148834018 644854700
947642099 255192490
35137537 134714230
944287156 528403260
68656286 200621680

样例输出 2

238630

样例输入 3

20
557057460 31783488
843507940 794587200
640711140 620259584
1901220 499867584
190122000 41414848
349507610 620259584
890404700 609665088
392918800 211889920
507308870 722352000
156850650 498904448
806117280 862969856
193607570 992030080
660673950 422816704
622015810 563434560
207866720 316871744
63057130 117502592
482593010 366954816
605221700 705015552
702500790 900532160
171743540 353470912

样例输出 3

152594452160

数据范围

对于所有数据，$1\le N\le50$，$1\le a_i,b_i\le10^9$。