题目描述

给定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

备注

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