P9401 [POI 2020/2021 R3] Collector 2 / Kolekcjoner Bajtemonów 2

Translated from [XXVIII Olimpiada Informatyczna - stage III](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Kolekcjoner Bajtemonów 2](https://szkopul.edu.pl/problemset/problem/yI8VISW680r7ktJAPvA5QPkl/statement/). This is a sample judging problem.

You are given $n$ pairs of numbers. You need to make $n$ binary choices (choose one number from each pair), so that you end up with $n$ numbers, and maximize the $\gcd$ of these $n$ numbers.

The first line contains a positive integer $n$. The next $n$ lines each contain two integers $a_i, b_i$.

Output one number in one line: the maximum possible $\gcd$.

Constraints: for all testdata, $1 \leq n \leq 10^6$, $1 \leq a_i \leq 5 \times 10^5$, $1 \leq b_i < 2^{63}$. For the $42$ pts testdata, $n \leq 5000$. Translated by ChatGPT 5