题目描述

给定$n$组非负整数$a_i, b_i$，求解关于$x$的方程组的最小非负整数解。 $$\begin{cases} x \equiv b_1 ({mod}\ a_1)\\ x \equiv b_2 ({mod}\ a_2)\\ ... \\ x \equiv b_n ({mod}\ a_n) \end{cases}$$

输入输出格式

输入格式

输入第一行包含整数$n$。

接下来$n$行，每行两个非负整数$a_i, b_i$。

输出格式

输出一行，为满足条件的最小非负整数$x$。

输入输出样例

输入样例 #1

3
11 6
25 9
33 17

输出样例 #1

809

说明/提示

对于$100 \%$的数据，$1 \le n \le {10}^5$，$1 \le b_i,a_i \le {10}^{12}$，保证所有$a_i$的最小公倍数不超过${10}^{18}$。

请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。

数据保证有解。