Bajtemon Collector 2

Bajtazar has a huge collection of Bajtemon cards. Each card shows a Bajtemon and lists its power before and after evolution. Bajtazar wants to sell the collection. Under the Bajtocko-Bitocki Agreement on Bajtemon Card Trading, the price of a collection is proportional to the greatest common divisor (GCD) of the powers of all Bajtemons in the deck. The agreement did not account for cards with two powers, so for each card Bajtazar may choose whether to count the power before or after evolution. He wants the GCD to be as large as possible. Write a program that finds the maximum price at which he can sell his collection.

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of cards. Each of the next $n$ 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. They are the power of the i-th Bajtemon before and after evolution. The power after evolution may be smaller than the power before evolution.

Print one integer, the maximum possible GCD of the Bajtemon powers that Bajtazar can obtain.

In the example, Bajtazar picks the powers after evolution for the third and fourth Bajtemons, and the powers before evolution for the first and second. The resulting powers are 5, 10, 20, and 5, so their GCD is 5.