题目描述

我们有一个红色袋子、一个蓝色袋子和 $N$ 个卡包。初始时，两个袋子都是空的。每个卡包包含两张上面写有整数的卡片。我们知道第 $i$ 个卡包中包含有数字 $a_i$ 和 $b_i$ 的两张卡片。

对于每个卡包，我们将其中一张卡片放入红袋子，另一张放入蓝袋子。

在我们将所有卡片放入袋子之后，设 $X$ 为红袋子中所有卡片上的整数的最大公约数，$Y$ 为蓝袋子中所有卡片上的整数的最大公约数。我们的得分将是 $X$ 和 $Y$ 的最小公倍数。

找到可能的最大得分。

约束条件

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

输入

输入以以下格式从标准输入中给出：

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

输出

打印可能的最大得分。

示例输入 1

2
2 15
10 6

示例输出 1

10

在这个示例中，一种最佳策略是将数字 $2$ 的卡片放入红袋子，将数字 $15$ 的卡片放入蓝袋子，将数字 $6$ 的卡片放入红袋子，将数字 $10$ 的卡片放入蓝袋子。 然后，红袋子中所有数字的最大公约数为 $2$，蓝袋子中所有数字的最大公约数为 $5$。 得分将为 $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