对于一些二元数对$[(a_1,b_1),(a_2,b_2)\cdots]$，定义它们的wcd为满足如下条件的数：

1. 这个数不为1.
2. 对于每个二元数对，这个数至少是其中一个数的因数.

例如$[(12, 15), (25, 18), (10, 24)]$的wcd可以是2,3,5,6。

显然，满足条件的数可能有很多，也可能没有。

现在CZY给了你一些二元数对，求出它们的wcd。

输入格式

第一行一个数n，表示二元数对的个数。

接下来n行，每行两个数$(a_i,b_i)$，表示一个二元数对。

输出格式

如果wcd存在，输出任意一个，否则输出-1。

输入输出样例

样例输入1

3
17 18
15 24
12 15

样例输出1

6

数据范围

由于某些特殊原因，本题采用捆绑测试。

子任务1：$30$分，$n\le 10$,$a_i,b_i\le 10^5$。

子任务2：$70$分，$n\le 150000,a_i,b_i\le 2\cdot 10^9$。