题目描述

物不知数问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便可知。

上述问题是指，求满足以下条件的整数：除以$3$余$2$，除以$5$余$3$，除以$7$余$2$。

而解法口诀则指的是这样的过程：$2\times 70+3\times 21+2\times 15=233=2\times 105+23$，则答案为$23$。

现在，给出这样$n$个条件，这个整数除以$a_i$余$b_i$，求满足条件的最小正整数。

题目保证给出的$a_i$两两互质。

输入格式

第一行输入一个整数$n$。 接下来$n$行，每行输入两个整数$a_i,b_i$。

输出格式

输出一行一个正整数，表示你的答案。

样例输入 #1

3
3 2
5 3
7 2

样例输出 #1

23

说明/提示

有$1\leq n\leq 10,0\leq b_i<a_i\leq 10^5,1\leq\prod a_i\leq 10^{18}$。