Smallest Nonnegative Integer Solution of Modular Equations

Given n pairs of nonnegative integers (a_i) and (b_i), find the smallest nonnegative integer (x) that satisfies the following system of congruences:

[ \begin{cases} x \equiv b_1 \pmod{a_1}\ x \equiv b_2 \pmod{a_2}\ \vdots \ x \equiv b_n \pmod{a_n} \end{cases} ]

It is guaranteed that a solution exists.

inputFormat

The first line contains an integer n (n ≥ 1).

Each of the following n lines contains two nonnegative integers a_i and b_i separated by a space.

outputFormat

Output the smallest nonnegative integer x that satisfies all of the modular equations.

sample

2
3 2
5 3

8