### 问题描述

在古代，有一种特殊的时间仪器，这种仪器可以通过不同的时间周期来预测未来。在某次考古发掘中，考古学家发现了这样一种古代仪器的碎片，但是他们不知道如何解读其中的信息。

这个仪器的工作原理是这样的：仪器上指针指向的时间总是减小的，假设其时间周期为 $7$，当指针指向 $0$ 后再次减少将会指向 $6$。每个时间周期代表一个固定的天数，例如一个周期是 $7$ 天，那么当时间经过 $7$ 天后，仪器上的指针就会归零。而每个仪器都有自己的时间周期以及初始偏移量，表示该仪器指针旋转一圈所需的天数，以及初始指针的位置。

考古学家想知道，为了使所有的指针都同时指向零点，他们需要等待多少天？你能帮忙解决这个问题吗？

输入格式

第一行包含一个整数 $n$ 表示时间仪器的数量。接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示一个周期为 $a_i$ 天，初始偏移量为 $b_i$ 天，题目保证输入的每个周期互质。

输出格式

输出包含一个正整数，表示等待多少天后，所有的时间仪器指针都将指向归零。

样例输入

3
3 1
5 1
7 2

样例输出

16

测评数据规模

$1 \leq n\le10$，$0 \leq b_i\lt a_i\leq 10^5$，$1 \leq \prod a_i \leq 10^{18}$。