Background

Translated from XXVIII Olimpiada Informatyczna - stage III Kolekcjoner Bajtemonów 2.

This is a sample judging problem.

Problem Description

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.

Input Format

The first line contains a positive integer $n$.

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

Output Format

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

4
5 7
10 15
13 20
7 5

5

2
18900 22050
14700 17640

7350

见附件

2

Hint

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