핫도그 노점 분산

동서로 아주 길게 뻗은 도로가 있고, 그 도로의 교차로마다 핫도그 노점이 장사를 시작했다. 문제는 한 교차로에 노점이 여럿 모이면 서로 손님을 빼앗는다는 것이다. 다행히 노점 주인들에게는 계획이 있다.

한 교차로에 노점이 두 개 이상 있으면, 그중 정확히 두 개가 이동을 한 번 수행할 수 있다. 이동은 다음과 같다.

• 한 노점은 도로를 따라 동쪽으로 한 교차로 옮겨 간다.
• 다른 한 노점은 도로를 따라 서쪽으로 한 교차로 옮겨 간다.

도로가 워낙 길어서 교차로가 모자랄 일은 없다. 모든 노점의 시작 위치가 주어진다. 노점이 전부 서로 다른 교차로에 놓일 때까지 필요한 이동의 최소 횟수를 구하라.

예를 들어 서쪽에서 동쪽 순서로 각 교차로의 노점 수가 0 0 2 1 2 0 0이라고 하자. 이때는 이동 세 번으로 모든 노점을 떼어놓을 수 있다.

... 0 0 2 1 2 0 0 ...
        |
        +--- 여기서 이동

... 0 1 0 2 2 0 0 ...
          |
          +--- 여기서 이동

... 0 1 1 0 3 0 0 ...
            |
            +--- 여기서 이동

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

각 교차로에는 정수 번호가 붙어 있고, 음수 번호도 쓴다. 교차로 i의 동쪽 바로 옆 교차로는 i+1이다. 입력은 이 번호로 교차로를 가리킨다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 시작 상태에서 노점이 하나 이상 있는 교차로의 수 $C$가 주어진다. 다음 $C$개의 줄에는 두 정수 $P$와 $V$가 공백으로 구분되어 주어지고, 교차로 $P$에 노점이 $V$개 있다는 뜻이다.

제한

• $1 \le T \le 50$
• $1 \le C \le 200$
• $-1000000 \le P \le 1000000$
• 한 테스트 케이스 안에서 $P$는 모두 다르고, 증가하는 순서로 주어진다.
• $V$는 양의 정수이고, 한 테스트 케이스의 $V$ 합은 $100000$ 이하이다.
• 유한한 횟수의 이동으로 노점을 항상 모두 떼어놓을 수 있다.

각 테스트 케이스마다 Case #x: M 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $M$은 모든 노점이 서로 다른 교차로에 놓이기까지 필요한 이동의 최소 횟수이다.