Hot Dog Proliferation

Hot dog vendors have started selling at the corners (intersections) of a very long east-west street. The trouble is that several vendors may end up on the same corner, and then they take each other's customers. The vendors have a plan for that.

Whenever a corner holds two or more vendors, exactly two of them can perform a move. A move works like this.

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

The street is really long, so the vendors never run out of corners. You are given the starting position of every vendor. Find the minimum number of moves needed until all vendors sit on different corners.

For example, suppose the number of vendors on each corner, listed from west to east, is 0 0 2 1 2 0 0. Three moves separate them.

... 0 0 2 1 2 0 0 ...
        |
        +--- move here

... 0 1 0 2 2 0 0 ...
          |
          +--- move here

... 0 1 1 0 3 0 0 ...
            |
            +--- move here

... 0 1 1 1 1 1 0 ...

Every corner carries an integer label, positive or negative. For each i, corner i+1 is the next corner east of corner i. The input describes corners with these labels.

The first line contains the number of test cases $T$. $T$ test cases follow. Each case begins with the number of corners $C$ that hold at least one vendor in the starting configuration. Each of the next $C$ lines contains two space-separated integers $P$ and $V$, meaning that corner $P$ holds $V$ vendors.

Limits

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

For each test case, print one line in the form Case #x: M, where $x$ is the test case number starting from 1 and $M$ is the minimum number of moves needed before all vendors end up on different corners.