题目描述

有一个 $N$ 项的数列 $A_1, \dots ,A_N$ 和 $N$ 个按钮。如果按下第 $i(1 \leq i \leq N)$ 个按钮，数列 $A$ 从第 $1$ 项到第 $i$ 项的值将各增加 $1$ 。

给出数列 $B_1, \dots ,B_N$ 。请问高桥君最少按几次按钮后，对于所有 $i$ ， $A_i$ 为 $B_i$ 的倍数？

数据范围

• 输入的所有数都为整数。
• $1 \leq N \leq 10^5$
• $0 \leq A_i \leq 10^9(1 \leq i \leq N)$
• $1 \leq B_i \leq 10^9(1 \leq i \leq N)$

输入

输入按以下形式：

N
A1 B1
:
AN BN

输出

输出一个数字，表示高桥君按按钮的最小次数。（行末换行）

样例

样例见原题面，另：样例1~2与样例3~4重复。

样例1解释

按第一个按钮 $2$ 次，第二个按钮 $2$ 次，第三个按钮 $3$ 次。