#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Chinese Remainder Theorem - Classic Problems | Repovive

CLS41. Chinese Remainder Theorem

1s256 MB

Given $n$ equations of the form: $x \equiv a_i \pmod{m_i}$

where all $m_i$ are pairwise coprime (their GCD is 1), find the smallest non-negative integer $x$ that satisfies all equations.

Constraints

$1 \le n \le 10$
$0 \le a_i < m_i$
$2 \le m_i \le 10^6$
All $m_i$ are pairwise coprime
The product $m_1 \cdot m_2 \cdot \ldots \cdot m_n \le 10^{18}$

Input

\begin{array}{l} n \\ a_1 \quad m_1 \\ a_2 \quad m_2 \\ \vdots \\ a_n \quad m_n \end{array}

Output

x

Samples

Input

Explanation

The value 23 satisfies all three equations: 23 mod 3 is 2, 23 mod 5 is 3, and 23 mod 7 is 2. No smaller non-negative value satisfies all three.

Output

Input

2
1 2
2 3

Explanation

The value 5 is 1 modulo 2 and 2 modulo 3. The smaller non-negative values 0 through 4 fail at least one equation.

Output

Input

Explanation

The value 0 satisfies all three equations because every required remainder is 0, so the smallest non-negative answer is 0.

Output

Given $n$ equations of the form: $x \equiv a_i \pmod{m_i}$

where all $m_i$ are pairwise coprime (their GCD is 1), find the smallest non-negative integer $x$ that satisfies all equations.

$1 \le n \le 10$
$0 \le a_i < m_i$
$2 \le m_i \le 10^6$
All $m_i$ are pairwise coprime
The product $m_1 \cdot m_2 \cdot \ldots \cdot m_n \le 10^{18}$

\begin{array}{l} n \\ a_1 \quad m_1 \\ a_2 \quad m_2 \\ \vdots \\ a_n \quad m_n \end{array}

x