Description

给你 $n$ 个数对，你要进行 $n$ 次二选一，这样你就有了 $n$ 个数，最大化这 $n$ 个数的 $\gcd$。

Input Format

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

接下来 $n$ 行，每行两个整数，$a_i,b_i$。

Output Format

一行一个数：最大的 $\gcd$。

4
5 7
10 15
13 20
7 5

5

2
18900 22050
14700 17640

7350

见附件

2

Hint

对于所有数据，$1\leq n\leq 10^6$，$1\leq a_i\leq 5\times 10^5$，$1\leq b_i<2^{63}$。

对于 $42pts$ 的数据，$n\leq 5000$。