配点 : $500$ 点

問題文

赤い袋と青い袋と $N$ 個のカードパックがあります。はじめどちらの袋も空です。 それぞれのカードパックには整数が書かれた $2$ 枚のカードが封入されており、$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$

出力

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

2
2 15
10 6

10

• $2$ が書かれたカードを赤い袋に入れ、$15$ が書かれたカードを青い袋に入れ、$6$ が書かれたカードを赤い袋に入れ、$10$ が書かれたカードを青い袋に入れるのが最適な入れ方の $1$ つです。
• このとき、赤い袋に入ったカードに書かれた整数全体の最大公約数は $2$、青い袋に入ったカードに書かれた整数全体の最大公約数は $5$ です。
• このときの得点は $10$ です。

5
148834018 644854700
947642099 255192490
35137537 134714230
944287156 528403260
68656286 200621680

238630

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