有三个岛屿 A、B 和 C，它们位于等边三角形的三个顶点上。 最初有 $n$ 名游客在岛屿 A 上。每名游客都有一个目的地岛屿 $w_i$，即岛屿 B 或岛屿 C。目前有一艘渡轮停靠在岛屿 A。渡轮的航线是固定的：$A \to B \to C \to A \to B \to C \to A \dots$

每名游客都有一个属性 $t_i$，代表在任意两个岛屿之间运送他们且不晕船所需的最短时间。渡轮同时最多只能搭载三个人。为了确保船上所有人都不会晕船，在任意两个岛屿之间航行所需的时间由船上所有人的 $t_i$ 中的最大值决定。

一旦游客到达目的地岛屿，他们就会留在岛上，不会再次登船。此外，游客只有在到达目的地时才会下船。如果船上没有人，渡轮就不能从码头出发，但幸运的是，我们在岛屿 A 上有无数名水手。这些水手训练有素，他们的属性均为 1，并且与游客不同，他们没有目的地，可以多次访问每个岛屿。

在将所有游客送达目的地岛屿后，所有水手和渡轮都必须回到岛屿 A。你需要找出实现这一目标所需的最短时间。

输入格式

第一行输入包含测试用例的数量 $T$ ($1 \le T \le 10$)。接下来是 $T$ 个测试用例。 对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 50000$)，代表游客人数。 在接下来的 $n$ 行中，每行包含两个整数描述一名游客。第一个整数 $w_i$ 代表游客的目的地岛屿，其中 $1$ 代表岛屿 B，$2$ 代表岛屿 C。第二个整数 $t_i$ ($1 \le t_i \le 1000$) 代表在任意两个岛屿之间运送该游客所需的最短时间。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将所有游客送达他们想去的岛屿所需的最短时间。

样例

输入 1

2
6
1 1
1 2
1 3
1 2
2 3
2 1
1
1 5

输出 1

Case #1: 14
Case #2: 7