Little Mark went to China and learned an ancient Chinese game dating from the 3^rd century. In this game every player chooses two numbers A, B (all pairs of numbers B must be coprime). The players gather around in a circle. Initially each player puts A beans in front of the player on his left. At this point each player writes down on their notebook the number of beans he has in front of him. Now the game starts by rounds. On every round each player will place B beans in front of the player at his right. Then each player writes down on their notebook the number of beans in front of them. The rounds keep going until there is a number C that all players have written on their notebook. The winner is the player with more numbers written before C.

For example, lets suppose there are three players, Mark, George and Mike. They choose the numbers 15 5, 17 8 and 16 7 respectively. Initially Mark would put 15 beans in front of Mike, George would put 11 beans in front of Mark and Mike would but 16 beans in front of George. Then everybody writes down the number in front of them (17, 16 and 15). Now on each round Mark will put 5 beans in front of George, George will put 8 beans in front of Mike, and Mike will put 7 beans in front of Mark. The following table summarizes the numbers written on each person’s notebook:

Mark  George  Mike
 17     16     15
 24     21     23
 31     26     31
 38     31     39

The last row of the table is the last round of the game, since the number 31 has already been written down by each player. So now the winner is George, since he has 3 numbers written before the 31.

Your task is to print the amount of numbers that the winner wrote before the common number C showed up. Since the game can get quite boring, in all the games the winner will have less than 2³¹ numbers written on his notebook.

Input

The input will begin with the number N of players (2 ≤ N ≤ 10). Following, there will be N lines, each containing a pair of numbers Ai, Bi (0 ≤ A ≤ 10⁶, 2 ≤ B ≤ 100) indicating the numbers A and B for player i.

The end of the input will be a case with N = 0.

Output

For each test case on the input you must print a line containing the amount of lines that the winner wrote before the common number C.

Example

Input:
3
15 5
17 8
16 7
2
1 2
1 3
0

Output:
3
0