Alice and Bob are playing a game of life, Alice is representing the evil character, and Bob is representing the good character; the game requires the evil to make a ritual in order to rule the world; Bob, being the good character, he tries to stop Alice from making this ritual.

The ritual consists of m gears that can rotate in only one direction, that is clockwise direction; each gear has a pointer pointing to one of its holes; the i^th gear contains n_i holes; in order to make the ritual, all the gears must be on their starting position. The configuration of the gears was ready to make the ritual, but unfortunately for Alice, Bob rotated the gears by some number of pushes, precisely he pushed the i^th gear by a_i holes, then he changed the system of the gears, and made it with one global control for all the gears, so that the only move Alice can make is to push all the gears at the same time by one hole for each gear. Since it will take too much time to complete the ritual, Alice thought of bringing some workers to finish the task for her as soon as possible, given that they all do the same amount of work. Alice wants to know in how many ways can she do this.

It's guaranteed that the minimum positive number of moves Alice can make, so it can restore the gears from the current configuration to Bob's configuration again, will not exceed 10¹⁴; and it is also guaranteed that Bob's configuration isn't the original configuration.

Sample input 1, the first gear rotated clockwise by 2 pushes, and the second gear rotated clockwise by 5 pushes.

Input

For each input file, the first line contains a single integer m (1 <= m <= 10³), the number of gears, and each of the next m lines contains two integers, the i^th line contain the two integers a_i and n_i space separated (0 <= a_i < n_i < 10¹⁴).

Output

For each test case, output a line containing a single integer, the number of ways to get an amount of workers, such that each does the same amount of work so they can solve the ritual.

Example

Input:
2
2 3
5 7

Output:
5

Input:
2
2 6
3 4

Output:
0

In the first case, the ritual can be completed after 16 pushes, so Alice can bring 1, 2, 4, 8, or 16 workers. In the second case, the ritual cannot be completed.