题目描述

给定 $n$ 组同余方程：

求最小的正整数 $x$ 满足所有方程，或者判断无解。

输入格式

输入包含多组数据。
每组数据第一行为整数 $n$。
接下来 $n$ 行，每行两个整数 $m_i, a_i$。

输出格式

对于每组数据，输出一行：
若无解，输出 $-1$；
否则输出最小的非负整数解。

2
8 7
11 9

31

数据规模与约定

对于全部的测试数据：

• $1 \leq n \leq 10^5$
• $m_i > a_i$
• 所有输入可用 64 位有符号整数表示