[ARC124C] LCM of GCDs

题意翻译

有 $N$ 组写了数字的卡片每组两张，每组卡片需要各放一张到两个袋子中，令两个袋子里数的最大公约数分别为 $X$ 和 $Y$ ，求 $X$ 和 $Y$ 的最小公倍数的最大值。

题目描述

[problemUrl]: https://atcoder.jp/contests/arc124/tasks/arc124_c 赤い袋と青い袋と $ N $ 個のカードパックがあります。はじめどちらの袋も空です。それぞれのカードパックには整数が書かれた $ 2 $ 枚のカードが封入されており、$ i $ 番目のカードパックに入っているカードにはそれぞれ $ a_i,b_i $ が書かれていることがわかっています。それぞれのカードパックについて、一方のカードを赤い袋に、他方のカードを青い袋に入れます。カードを袋に入れ終えたのち、赤い袋に入ったカードに書かれた整数全体の最大公約数を $ X $ とします。同様に、青い袋に入ったカードに書かれた整数全体の最大公約数を $ Y $ とします。 $ X $ と $ Y $ の最小公倍数の値が得点となります。得点としてありうる値の最大値を求めてください。

输入输出格式

输入格式

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_N $ $ b_N $

输出格式

得点としてありうる値の最大値を出力せよ。

输入输出样例

输入样例 #1

2
2 15
10 6

输出样例 #1

输入样例 #2

5
148834018 644854700
947642099 255192490
35137537 134714230
944287156 528403260
68656286 200621680

输出样例 #2

输入样例 #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\ \leq\ N\ \leq\ 50 $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ 10^9 $ ### Sample Explanation 1 \- $ 2 $ が書かれたカードを赤い袋に入れ、$ 15 $ が書かれたカードを青い袋に入れ、$ 6 $ が書かれたカードを赤い袋に入れ、$ 10 $ が書かれたカードを青い袋に入れるのが最適な入れ方の $ 1 $ つです。 - このとき、赤い袋に入ったカードに書かれた整数全体の最大公約数は $ 2 $、青い袋に入ったカードに書かれた整数全体の最大公約数は $ 5 $ です。 - このときの得点は $ 10 $ です。