#R2024A0602. 同余3

同余3

同余3

题目背景

lhy 出数据出麻了, 所以来再水点题.

题目描述

给定k个二元组,第i个为ai,bia_i,b_i, 找到所有 n 使得 aibi(mod n)a_i \equiv b_i \quad (mod~n). 保证 aibia_i \neq b_i.

数据格式

输入

第一行, 一个正整数 k.

接下来 k 行, 每行两个正整数 ai,bia_i,b_i.

输出

一行, 输出所有符合条件的 n.

样例

输入

3
12 34
56 78
90 12

输出

1 2

数据范围及约定

k105k \le 10^5

1ai,bi1091 \le a_i,b_i \le 10^9.