Common Element

Create a program to find the smallest natural number that is a member of all given $n$ infinite arithmetic progressions of natural numbers.

Input

The input consists of (2n + 1) non-negative integers. The first integer is $n$, where n < 100. For each $j$-th pair of numbers following $n$, the first number represents the first term of the $j$-th progression, and the second number is the common difference. All numbers are no greater than $10000$.

Output

Output the smallest number that belongs to all progressions. If no such number exists, output 0.