Description

Since Cao Chong successfully dealt with the elephant, Cao Cao began to think about getting his son involved in some business. He sent him to a pig farm in the Central Plains to raise pigs. However, Cao Chong was unhappy and thus worked carelessly. Once, Cao Cao wanted to know the number of sows, so Cao Chong decided to play a trick on him.

For example, suppose there are $16$ sows. If $3$ pig pens are built, $1$ sow is left without a home; if $5$ pig pens are built, there is still $1$ sow without a place; if $7$ pig pens are built, $2$ sows are left without a place. As Cao Cao's personal secretary, it is your duty to report the accurate number of pigs to him. What should you do?

Input Format

The first line contains an integer $n$, indicating the number of times pig pens were built.

The next $n$ lines each contain two integers $a_i$ and $b_i$, indicating that $a_i$ pig pens were built, and $b_i$ sows were left without a place. You may assume that $a_i$ and $a_j$ are coprime for any $i$ and $j$.

Output Format

Output only a single positive integer, which is the minimum number of sows Cao Chong raised.

Sample 1

3
3 1
5 1
7 2

16

Data Range and Hints

For all data, $1\le n\le 10, 1\le b_i\le a_i\le 1000$.