Reference: Codeforces 1025B — Weakened Common Divisor

You are given ~n~ pairs of integers:

~(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)~

A weakened common divisor of these pairs is an integer ~d > 1~ such that, for every pair ~(a_i, b_i)~, at least one of ~a_i~ or ~b_i~ is divisible by ~d~.

Find any weakened common divisor of the given pairs.

Input

• The first line contains one integer ~n~.
• Each of the next ~n~ lines contains two integers: ~a_i~ and ~b_i~.

Output

• Print one integer satisfying the required condition. When multiple answers exist, print any of them. If no such integer exists, print ~-1~.

Constraints

• ~1 \le n \le 150000~
• ~2 \le a_i, b_i \le 2 \times 10^9~

Example 1

Input:

3
17 18
15 24
12 15

Output:

6