Problem Description

There are $ N $ pairs of integers. The $ i $ -th pair of integers is $ (A_i, B_i) $.

Snuke is trying to choose exactly one integer from each pair. What is the maximum possible value of the greatest common divisor (GCD) of the $ N $ chosen integers?

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_N $ $ B_N $

Output Format

Output the maximum possible value of the greatest common divisor of the $ N $ integers chosen by Snuke.

Sample Input and Output

Sample Input #1

2
15 12
18 18

Sample Output #1

6

Sample Input #2

3
999999929 999999883
999999757 999999929
999999883 999999757

Sample Output #2

1

Notes/Hints

Constraints

The input satisfies the following conditions:

• $1 \leq N \leq 5 \times 10^4$
• $1 \leq A_i, B_i \leq 10^9$
• All values in the input are integers.

Sample Explanation 1

Choosing $ 12 $ and $ 18 $ from each pair respectively results in a greatest common divisor of $ 6 $, which is the maximum possible value.

见题面 Input 部分

见题面 Output 部分