Title
Problem Statement
There are an integer sequence A1,...,AN consisting of N terms, and N buttons.
When the i-th (1 ≦ i ≦ N) button is pressed, the values of the i terms from the first through the i-th are all incremented by 1.
There is also another integer sequence B1,...,BN. Takahashi will push the buttons some number of times so that for every i, Ai will be a multiple of Bi.
Find the minimum number of times Takahashi will press the buttons.
Constraints
- All input values are integers.
- 1 ≦ N ≦ 105
- 0 ≦ Ai ≦ 109(1 ≦ i ≦ N)
- 1 ≦ Bi ≦ 109(1 ≦ i ≦ N)
Input
The input is given from Standard Input in the following format:
N
A1 B1
:
AN BN
Output
Print an integer representing the minimum number of times Takahashi will press the buttons.
Sample Input 1
3
3 5
2 7
9 4
Sample Output 1
7
Press the first button twice, the second button twice and the third button three times.
Sample Input 2
7
3 1
4 1
5 9
2 6
5 3
5 8
9 7
Sample Output 2
22