给定 $2n$ 个整数 $a\_1,a\_2,…,a\_n$ 和 $m\_1,m\_2,…,m\_n$，求一个最小的非负整数 $x$，满足 $\forall i \in [1,n],x \equiv m\_i(mod\ a\_i)$。

输入格式

第 $1$ 行包含整数 $n$。

第 $2…n+1$ 行：第 $i+1$ 行包含两个整数 $a\_i$ 和 $m\_i$，数之间用空格隔开。

输出格式

输出最小非负整数 $x$，如果 $x$ 不存在，则输出 $-1$。

数据范围

$1 \le a\_i \le 2^{31}-1$,

$0 \le m\_i < a\_i$

$1 \le n \le 25$

所有 $m\_i$ 的最小公倍数在 $64$ 位有符号整数范围内。

Samples

2
8 7
11 9

31