Problem Description

You are given $n$ pairs of numbers. You need to make $n$ choices, one from each pair, resulting in $n$ numbers. Your goal is to maximize the greatest common divisor (GCD) of these $n$ numbers.

Input Format

The first line contains a single positive integer $n$.

The next $n$ lines each contain two integers, $a_i$ and $b_i$.

Output Format

Output a single number: the maximum GCD that can be achieved.

Sample Input and Output

Sample Input #1

4
5 7
10 15
13 20
7 5

Sample Output #1

5

Sample Input #2

2
18900 22050
14700 17640

Sample Output #2

7350

Sample Input #3

(Not provided in the original text)

Sample Output #3

2

Notes

For all test cases, $1 \leq n \leq 10^6$, $1 \leq a_i \leq 5 \times 10^5$, and $1 \leq b_i < 2^{63}$.

For $42$ points, $n \leq 5000$.

见题面 Input 部分

见题面 Output 部分