许多热狗摊贩开始在一条东西向长街的各个路口（交叉路口）售卖热狗。问题在于，多个摊贩可能会在同一个路口售卖，这样他们就会抢夺彼此的生意。不过，一切并非无可挽回！摊贩们有一个计划。
如果某个路口有两名或更多的摊贩，那么恰好两名摊贩可以执行一次移动，这意味着：
- 一名摊贩沿街道向东移动一个路口。
- 另一名摊贩沿街道向西移动一个路口。
例如，假设街道上各路口初始的热狗摊贩数量如下（按从西到东的顺序排列）：
... 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$ 指的是路口 $i$ 向东的下一个路口。我们将使用此标记系统来描述输入文件中的路口。
输入文件的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以起始配置中至少有一名热狗摊贩的路口数量 $C$ 开始。接下来的 $C$ 行，每行包含一对空格分隔的整数 $P$ 和 $V$，表示在路口 $P$ 有 $V$ 名摊贩。
输出格式
对于每个测试用例，输出一行 "Case #x: M"，其中 $x$ 是测试用例编号（从 1 开始），$M$ 是摊贩全部位于不同路口之前需要执行的最少移动次数。
数据范围
$1 \le T \le 50$
$1 \le C \le 200$
所有 $P$ 的值都在 $[-1000000, 1000000]$ 范围内。
在每个测试用例中，所有 $P$ 的值都是不同的，并按升序排列。
所有 $V$ 的值均为正整数。所有 $V$ 的总和限制如下。
总能通过有限次数的移动将热狗摊贩分开。
小数据集（测试集 1 - 可见；6 分）
每个测试用例中的热狗摊贩总数最多为 200。
大数据集（测试集 2 - 隐藏；22 分）
每个测试用例中的热狗摊贩总数最多为 100000。
样例
样例输入 1
2 3 -1 2 0 1 1 2 2 -1000 1 2000 1
样例输出 1
Case #1: 3 Case #2: 0