编程题
### 问题描述
此题为中国剩余定理模板题，前置知识：扩展欧几里得定理 ，乘法逆元。
中国剩余定理可求解如下形式的一元线性同余方程组（其中 $m_1, m_2 \dots m_k $ 两两互质）：
$$
\begin{cases}
x \equiv a_1 & (\mod m_1)\\\\
x \equiv a_2 & (\mod m_2)\\\\
& \dots\\\\
x \equiv a_n & (\mod m_n)
\end{cases}
$$
现给定 $n, m_1\dots m_n, a_1\dots a_n$, 求解满足上述要求的最小正整数 $x$。
### 输入格式
第一行，包含一个正整数 $n$。
接下来有 $n$ 行，每行两个正整数 $m_i, a_i$。
### 输出格式
输出仅一行，包含一个整数，表示答案。
### 样例输入
```text
3
9 8
4 2
25 1
```
### 样例输出
```text
26
```
### 评测数据规模
对于 $100$% 的评测数据，$2\leq n,2\leq m_i, \prod_{i=1}^n m_i \le 10^9$。