你的公司刚刚建成了一座摩天大楼，但你发现了一个严重的问题：每一层楼只能容纳一个游戏室！游戏室尚未装修，因此你仍然可以决定哪些楼层设为乒乓球室，哪些楼层设为台球室。大楼内每种类型的游戏室必须至少各有一个。

幸运的是，你知道谁将在大楼的哪个位置工作（每个人都已经选好了办公室）。你知道每一层楼有 $T_i$ 名乒乓球爱好者和 $P_i$ 名台球爱好者。我们的目标是最小化每位员工到其所需类型游戏室的距离之和。距离定义为楼层编号之差：如果员工所在的楼层就有他们所需类型的游戏室，则距离为 0；如果所需类型的最近游戏室在员工所在楼层的上一层或下一层，则距离为 1，以此类推。

输入格式

输入的第一行包含测试用例的数量 $T(1 \le T \le 100)$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N(2 \le N \le 4000)$，表示大楼的楼层数。接下来的 $N$ 行，每行包含两个整数 $T_i$ 和 $P_i(1 \le T_i, P_i \le 10^9)$，分别表示第 $i$ 层楼的乒乓球爱好者和台球爱好者人数。输入按楼层编号从 1 到 $N$ 递增的顺序给出。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最小的距离之和。

样例

输入 1

1
2
10 5
4 3

输出 1

Case #1: 9

说明

在第一个样例中，你可以在第一层楼建立一个乒乓球室，在第二层楼建立一个台球室。在这种情况下，第一层楼的 5 名台球爱好者需要上一层楼，第二层楼的 4 名乒乓球爱好者需要下一层楼。因此总距离为 9。