题目描述

有一个红色袋子、一个蓝色袋子和 $N$ 个卡包。开始时两个袋子都是空的。每个卡包中都封有两张写有整数的卡片，第 $i$ 个卡包中的两张卡片分别写有 $a_i$ 和 $b_i$。

对于每一个卡包，你需要将其中一张卡片放入红色袋子，另一张放入蓝色袋子。

所有卡片都放入袋子后，红色袋子中所有卡片上的整数的最大公约数记为 $X$，蓝色袋子中所有卡片上的整数的最大公约数记为 $Y$。$X$ 和 $Y$ 的最小公倍数即为得分。

请你求出作为得分可能取得的最大值。

输入格式

输入按以下格式从标准输入读入。

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_N$ $b_N$

输出格式

输出作为得分可能取得的最大值。

样例 1

输入

2
2 15
10 6

输出

10

样例 2

输入

5
148834018 644854700
947642099 255192490
35137537 134714230
944287156 528403260
68656286 200621680

输出

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

输出

152594452160

说明/提示

限制

• 所有输入均为整数。
• $1 \leq N \leq 50$
• $1 \leq a_i, b_i \leq 10^9$

样例解释 1

• 一种最优的放法是：将写有 $2$ 的卡片放入红色袋子，将写有 $15$ 的卡片放入蓝色袋子，将写有 $6$ 的卡片放入红色袋子，将写有 $10$ 的卡片放入蓝色袋子。
• 此时，红色袋子中所有卡片上的整数的最大公约数为 $2$，蓝色袋子中所有卡片上的整数的最大公约数为 $5$。
• 此时的得分为 $10$。

由 ChatGPT 4.1 翻译