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 (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.

Examples