Description

Given $n$ pairs of non-negative integers $a_i, b_i$, find the smallest non-negative integer solution to the system of equations in $x$.

$$\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}$$

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two non-negative integers $a_i, b_i$.

Output Format

Output one line: the smallest non-negative integer $x$ that satisfies the conditions.

3
11 6
25 9
33 17

809

Hint

For $100\%$ of the testdata, $1 \le n \le {10}^5$, $1 \le a_i \le {10}^{12}$, $0\leq b_i \leq 10^{12}$. It is guaranteed that the least common multiple of all $a_i$ does not exceed ${10}^{18}$.

Please note that during the execution of the program, multiplication operations may overflow.

It is guaranteed that a solution exists.

Translated by ChatGPT 5