Strange Way to Express Integers

Strange Way to Express Integers

Description

给定2n个正整数 a1,a2,...,an 和 r1,r2,...,rn,求一个最小的正整数 x,满足∀ i∈[1,n],x≡ai(mod ri),或者给出无解。

Format

Input

多组数据。
每组数据第一行一个整数k。
接下来k行,每行两个整数 ai,ri。

Output

对于每组数据,若无解,输出“-1”;否则,输出一个非负整数,若有多解,输出最小的满足条件的答案。

Sample 1

Input

2
8 7
11 9

Output

31

Limitation

1s,128MiB for each test case.

Source

poj2891