Bajtazar has a huge collection of Bajtemon cards. Each card in his deck features a Bajtemon and its power level both before and after evolution. Bajtazar has decided to sell his collection. According to the Bajtocko-Bitocki Agreement on Bajtemon Card Trading, the cost of the collection is proportional to the greatest common divisor (GCD) of the power levels of all Bajtemons in the deck. However, this agreement did not foresee the existence of cards with more than one power level listed, so for each card, Bajtazar can choose whether to use the Bajtemon's power before or after evolution.

He naturally wants to do this in such a way that the resulting GCD is as large as possible. Write a program that will help him determine the maximum price at which he can sell his collection.

Input

The first line of input contains an integer $n$ ($1 \le n \le 10^6$) representing the number of cards in Bajtazar's collection. The next $n$ lines contain the descriptions of the Bajtemons; the $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le 5 \cdot 10^5$, $1 \le b_i < 2^{63}$) separated by a single space, representing the power of the $i$-th Bajtemon before and after evolution, respectively. It may happen that the power after evolution is smaller than the power before evolution.

Output

The first and only line of output should contain a single integer representing the maximum possible GCD of the Bajtemon power levels that Bajtazar can obtain.

Examples

Input 1

4
5 7
10 15
13 20
7 5

Output 1

5

Note

If Bajtazar chooses the power of the third and fourth Bajtemon after evolution, and the first and second before evolution, then the consecutive Bajtemons will have powers 5, 10, 20, and 5, so their GCD will be equal to 5.

Evaluation tests

• Test 1: $n = 2$; $a_1 = 18900, b_1 = 22050, a_2 = 14700, b_2 = 17640$; answer is 7350.
• Test 2: $n = 100\,000$; $a_i = 100\,000 + i, b_i = 100\,001 + i$; answer is 2.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.