该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

小爱拿到了 $n$ 张卡片，每张卡片的正反面均写有一个数字，其中第 $i$ 卡片的正面的数字为 $a_i$ ，反面的数字为 $b_i$ ​。

他可以翻转任何卡片任意多次。

所有卡片的正面数字和反面数字分别求一个最大公约数，问这两个最大公约数的最小公倍数的最大值是多少？

Format

Input

第一行，一个正整数 $n（\le50）$ 。

接下来 $n$ 行，每行两个整数 $a_i、b_i$ ，每个整数的不超过 $10^9$ 。

Output

输出共一行，一个整数，所能获得的最大值。

Samples

3
114 514
11 14
51 54

2

Limitation

1s, 1024KiB for each test case.