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

输入格式

多组数据。

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

输出格式

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

样例

输入样例

2
8 7
11 9

输出样例

31

数据范围与提示

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