Number Theory—Homework Problem #1—Klanta Sauce Strikes Again

Problem: numtheory1

As all of us know, Santa is always very busy trying to service the needs of 6.76 billion people around the world. To facilitate his work, he has constructed a series of carousels that goes through his Christmas factory. Anything—presents, coal, somebody's lunch, lost elves—can be transported on this system.

Unfortunately, "anything" also includes bombs, and Klanta Sauce has made use of this fact. In order to destroy the happiness of every child on the planet, he has attached a bomb on every gear that is present in the system. To maximize the damage, on every gear he has marked a point where the bomb will cause the most damage. When every bomb is simultaneously present on its mark, the bombs will explode together.

For the purposes of this problem, assume that there are G gears in the system. The i^th gear is connected only to the (i-1)^th gear and (i+1)^th gear. An engine drives the first gear to rotate clockwise at the speed of one tooth per time step. Since the gears are connected to each other, they will all rotate at the same speed of one tooth per time step (although not necessarily in the same direction).

You are given t_i (1 ≤ i ≤ G, 1 < t_i), the number of teeth on each gear, and b_i (1 ≤ i ≤ G, 0 ≤ b_i < t_i), the current location of the bomb on the i^th gear described by the number of teeth counterclockwise from its mark (its intended location of explosion). The bomb sticks to the gear, and hence rotates at the same speed as the gear. The bombs will explode simultaneously when every bomb is on its mark. (A schematic is given after the sample output.)

Santa has heard about your amazing coding abilities, and he has implored you to write a program to calculate the number of time steps before the bomb explodes, so he can plan for a course of action. Remember, Christmas itself is at stake.

Input

The input consists of multiple test cases. The first line in the input will contain a single number N, the number of test cases. The first line of each test case will be a single integer G > 0, the number of gears. Then G lines of input will follow; the i^th line will contain two integers, t_i and b_i, as described above. You may assume t_i and b_i will both fit into 32-bit signed integers.

Output

For each test case, output should be an integer k on its own line, where k is the number of time steps that will elapse before the bombs explode. You may assume that k can always fit into a 64-bit signed integer. If the bombs will never explode, output Klanta Sauce has screwed up! instead.

Sample Input

3
3
10 2
20 8
10 2
3
5 2
4 2
6 4
2
4 3
6 0

Sample Output

12
22
Klanta Sauce has screwed up!

Diagram