熊猫先生住在熊猫乐园。熊猫乐园里有许多城市，每个城市都可以看作二维平面上的一个点。不同的城市位于不同的位置。

乐园里还有 $M$ 条连接这些城市的双向道路。除了端点外，任意两条不同的道路之间没有交点。此外，每条道路都有一个权值 $w$。

有一天，熊猫先生想在熊猫乐园中找到一个权值最小的简单环。简单环是指一条起点和终点相同，且每条道路最多经过一次的路径。环的权值是它所包含的所有道路的权值之和。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例以一个整数 $M$ 开头。 接下来的 $M$ 行描述了熊猫乐园中的道路。 每行包含 5 个整数 $x_1, y_1, x_2, y_2, w$，表示有一条权值为 $w$ 的道路连接坐标为 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的城市。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是熊猫先生想知道的最小环权值。 如果地图中不存在环，则 $y$ 为 0。

数据范围

• $1 \le T \le 50$
• $1 \le m \le 4000$
• $-10000 \le x_i, y_i \le 10000$
• $1 \le w \le 10^5$

样例

样例输入 1

2
5
0 0 0 1 2
0 0 1 0 2
0 1 1 1 2
1 0 1 1 2
1 0 0 1 5
9
1 1 3 1 1
1 1 1 3 2
3 1 3 3 2
1 3 3 3 1
1 1 2 2 2
2 2 3 3 3
3 1 2 2 1
2 2 1 3 2
4 1 5 1 4

样例输出 1

Case #1: 8
Case #2: 4