题目描述

给定2n个正整数$a_1,a_2, \cdots,a_n$和$m_1,m_2, \cdots,m_n$，求一个最小的正整数x，满足$\forall i \in[1,n],x \equiv a_i \ ( \bmod m_i \ )$，或者给出无解。

输入描述

每组数据第一行一个整数n； 接下来n行，每行两个整数$m_i,a_i$。

输出描述

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

示例1

输入

2
8 7
11 9

输出

31

备注

输入样例 #2

4
69 53
31 5
99 42
89 34
2
18 12
71 7
4
29 28
18 4
18 10
28 7

输出样例 #2

-1
930
-1

输入样例 #3

3
27 13
36 4
62 30
3
91 26
62 49
80 15
4
79 51
53 51
53 25
42 15
5
80 54
83 1
19 18
16 7
71 6
2
22 21
34 27
3
16 8
41 40
63 36
3
85 7
83 5
37 3
4
33 14
89 11
44 12
31 4
3
23 9
80 9
15 12
3
64 11
72 6
9 5

输出样例 #3

2200
14495
-1
-1
197
38088
148077
-1
-1
-1

数据范围

对于全部数据，所有的输入都是非负的，并且可以用64位有符号整数表示。保证$1 \leq n \leq 10^5,m_i \gt a_i$。