GMLIFE - Game of Life

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 ith gear contains ni 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 ith gear by ai 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 1014; and it is also guaranteed that Bob's configuration isn't the original configuration.

 

Visualisation for first sample input.

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 <= 103), the number of gears, and each of the next m lines contains two integers, the ith line contain the two integers ai and ni space separated (0 <= ai < ni < 1014).

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.


Added by:Mostafa mahmoud
Date:2013-02-13
Time limit:0.200s-0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2013-02-22 02:06:14 :D
Moved to partial for now.
2013-02-22 02:06:14 Mitch Schwartz
How does scoring work? For classical problems, scoring should be set to binary, otherwise it will count as a challenge problem with respect to points/ranking.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.