Maximizing GCD from Pairs

You are given n pairs of positive integers. For each pair, you must choose exactly one number. Let the chosen numbers be \(x_1, x_2, \dots, x_n\). Your task is to maximize their greatest common divisor (\(\gcd(x_1,x_2,\dots,x_n)\)).

A valid selection satisfies that for every pair \((a, b)\), at least one of \(a\) or \(b\) is chosen. The answer is the maximum integer \(d\) such that there exists a selection where \(d\) divides every chosen number.

Hint: For the \(\gcd\) of the chosen numbers to be at least \(d\), it is necessary and sufficient that in each pair, at least one number is divisible by \(d\). Therefore, a candidate \(d\) must be a divisor of at least one of the numbers in the first pair.

inputFormat

The first line contains a single integer \(n\) (the number of pairs).
Each of the following \(n\) lines contains two positive integers \(a\) and \(b\), representing a pair.

Example:

3
10 4
3 6
8 10

outputFormat

Output a single integer, the maximum possible \(\gcd\) of the chosen numbers.

Example:

2

sample

3
10 4
3 6
8 10

2