AT_arc124_c [ARC124C] LCM of GCDs

有一个红色袋子、一个蓝色袋子和 $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 \leq N \leq 50$ - $1 \leq a_i, b_i \leq 10^9$ ## 样例解释 1 - 一种最优的放法是：将写有 $2$ 的卡片放入红色袋子，将写有 $15$ 的卡片放入蓝色袋子，将写有 $6$ 的卡片放入红色袋子，将写有 $10$ 的卡片放入蓝色袋子。 - 此时，红色袋子中所有卡片上的整数的最大公约数为 $2$，蓝色袋子中所有卡片上的整数的最大公约数为 $5$。 - 此时的得分为 $10$。 由 ChatGPT 4.1 翻译