题目描述

小 Z 班上的 $2n$ 名同学们都两两组成了 $n$ 对“干饭搭子”，即相熟的两名同学都会一起吃饭，每名同学都有一个“干饭值”。

现在班上要举行干饭比赛，规则是设置了 $2$ 个战队，为了比赛观赏性，每对搭子必须分属 $2$ 个战队（即两人不能在同一战队）。

两个战队各自都有 $n$ 名同学，战队内同学们干饭值的 $gcd$ 分别为 $x,y$，当 $lcm(x,y)$ 最大时比赛的观赏性最高。求解这个最大的 $lcm(x,y)$。

注：$gcd$ 是指最大公约数；$lcm(x,y)$ 是指 $x,y$ 的最小公倍数。

输入格式

第一行，$1$ 个正整数 $n$。

接下来 $n$ 行，每行 $2$ 个正整数，表示第 $i$ 对搭子两人的干饭值 $a_i,b_i$。

输出格式

$1$ 个整数，表示最大的 $lcm(x,y)$。

输入输出样例

2
2 15
10 6

10

样例 $\tt \#1$说明

• $2,6$ 作为第一队， $15,10$ 作为第二队时，$x=gcd(2,6)=2,y=gcd(15,10)=5$，此时 $lcm(x,y)=10$ 为最大的情况。

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

数据范围

• 对于 $30\%$ 的数据，$n\le20, a_i,b_i\le 10^3$
• 对于$80\%$ 的数据，$n\le50, a_i,b_i\le 10^3$
• 对于 $100\%$ 的数据，$1\le n\le50, 1\le a_i,b_i\le 10^9$