Background

Special for beginners, ^_^

Description

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

Format

Input

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

Output

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

Samples

2
8 7
11 9

31

Limitation

1s, 1024KiB for each test case.