A number of hot dog vendors have started selling hot dogs at corners (intersections) along a very long east-west street. The problem is that multiple vendors might be selling at the same corner, and then they will take each other's business. All is not lost though! The hot dog vendors have a plan.
If there are ever two or more vendors at the same corner, then exactly two of the vendors can perform a move, which means:
For example, suppose the street begins with the following number of hot dog vendors on each corner, listed in order from west to east:
... 0 0 2 1 2 0 0 ...Then the vendors can be separated in three moves, as shown below:
... 0 0 2 1 2 0 0 ... | +--- Do a move here ... 0 1 0 2 2 0 0 ... | +--- Do a move here ... 0 1 1 0 3 0 0 ... | +--- Do a move here ... 0 1 1 1 1 1 0 ...
Each street corner is labeled with an integer, positive or negative. For each
i+1 refers to the next corner to the east from corner
i. We will use this labeling system to describe corners in the input file.
The first line of the input file contains the number of cases, T. T test cases follow. Each case begins with the number of corners C that have at least one hot dog vendor in the starting configuration. The next C lines each contain a pair of space-separated integers P, V, indicating that there are V vendors at corner P.
For each test case, output one line containing "Case #x: M", where x is the case number (starting from 1) and M is the minimum number of moves that need to be performed before the vendors all end up at different corners from each other.
1 ≤ T ≤ 50.
1 ≤ C ≤ 200.
All P values are in the range [-1000000, 1000000].
Within each test case, all P values are distinct and listed in increasing order.
All V values are positive integers. The limit on the sum of all V values is listed below.
It will always be possible to separate the hot dog vendors in a finite number of moves.
The total number of hot dog vendors in each test case is at most 200.
The total number of hot dog vendors in each test case is at most 100000.