Description

Original source: POJ 2891

Given $2n$ positive integers $a_1,a_2,\cdots ,a_n$ and $m_1,m_2,\cdots ,m_n$, find the smallest positive integer $x$ such that $\forall i\in[1,n],x\equiv a_i\ (\bmod m_i\ )$, or determine that no solution exists.

Input Format

Multiple test cases.

For each test case, the first line contains an integer $n$;
The next $n$ lines each contain two integers $m_i,a_i$.

Output Format

For each test case, if no solution exists, output $-1$; otherwise, output a non-negative integer. If there are multiple solutions, output the smallest valid answer.

Sample 1

2
8 7
11 9

31

Data Range and Hints

For all data, all inputs are non-negative and can be represented by a 64-bit signed integer. It is guaranteed that $1\le n\le 10^5$ and $m_i\gt a_i$.