Hot Dog Proliferation (Small)

Hot dog vendors have set up at the corners (intersections) of a very long east-west street. The trouble is that several vendors can end up at the same corner, and then they take business from each other. There is still a way out. The vendors have a plan.

Whenever a corner holds two or more vendors, exactly two of them can perform a move, which means:

• One vendor goes one corner further east along the street.
• The other vendor goes one corner further west along the street.

The street is really long, so the vendors never run out of corners. Given the starting positions of all hot dog vendors, find the minimum number of moves they need to perform before the vendors are all separated, meaning they are all on different corners.

For example, suppose the number of hot dog vendors on each corner, listed in order from west to east, starts like this.

... 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$, corner $i+1$ is the next corner to the east from corner $i$. The input uses this labeling to describe corners.

The first line 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$ and $V$, indicating that there are $V$ vendors at corner $P$.

Limits

• $1 \le T \le 50$
• $1 \le C \le 200$
• $-1000000 \le P \le 1000000$
• Within each test case all $P$ values are distinct and listed in increasing order.
• Each $V$ is a positive integer, and the sum of all $V$ values in one test case, the total number of vendors, is at most 200.
• It is always possible to separate the hot dog vendors in a finite number of moves.

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.