Farmer John 在他的农场里建造了 $n$ 道栅栏。第 $i$ 道栅栏是平面上的一条线段，其两个端点分别为 $(x_{1i}, y_{1i})$ 和 $(x_{2i}, y_{2i})$。不同的栅栏仅能在端点处相交。下图展示了一个栅栏布局的示例。

fence1, fence2, fence3, fence4, fence5, p1=p2=p3=p4=1, p5=100

为了让奶牛们开心，John 将用绳灯装饰这些栅栏。一道栅栏上可以悬挂多条与自身平行的绳灯。然而，灯不能单独使用。John 只能通过将一些灯组合在一起（我们称之为“灯串”）来进行装饰，这些灯将形成一个环来装饰某些栅栏（一盏灯对应一道栅栏）。在示例中，他可以使用三盏灯来装饰编号为 1, 2, 5 的三道栅栏，它们构成一个环。

装饰编号为 $k_1, k_2, \dots, k_m$ 的栅栏的灯串，其花费为 $\sum_{i=1}^m p_{k_i}$ 美元。总花费是每条灯串花费的总和。注意，如果使用多条灯串，其花费应当累加。在示例中，假设他用两条灯串装饰栅栏。一条灯串装饰编号为 1, 2, 5 的三道栅栏，另一条灯串装饰编号为 1, 2, 3, 4 的四道栅栏。那么总花费应为 $2 \times p_1 + 2 \times p_2 + p_3 + p_4 + p_5 = 106$ 美元。

John 可以控制每条灯串的开关。他可以打开某条灯串上的所有灯，或者关闭所有灯，但他不能只打开其中一部分而保持该灯串上的其他灯关闭。对于一道栅栏，如果其上处于开启状态的灯串数量为偶数，则该栅栏上的所有灯都不会工作；否则，所有灯都会工作。我们定义灯的“形状”为每道栅栏的状态组合（考虑栅栏是否被点亮）。一种灯的形状可以通过灯的排列来实现。下图展示了示例中所有可能的灯的形状。（虚线表示灯工作的栅栏，实线表示灯不工作的栅栏。）

奶牛们喜欢灯，但她们也很善变。她们希望每天灯的排列都能形成不同的形状，因此 John 需要安排装饰，使得通过打开某些灯串并关闭其他灯串，可以形成每一种可能的形状。John 为了满足奶牛的需求，最少需要花费多少钱？

在示例中，他可以用两条灯串装饰栅栏。一条灯串装饰编号为 1, 2, 5 的三道栅栏，另一条灯串装饰编号为 1, 2, 3, 4 的三道栅栏。如果他关闭所有灯串，奶牛们可以得到第一种形状；如果他打开所有灯串，奶牛们可以得到最后一种形状；如果他只打开第一条灯串，奶牛们可以得到第三种形状；如果他只打开第二条灯串，奶牛们可以得到第二种形状。因此，他可以花费 106 美元来满足奶牛的需求，这也恰好是最小花费。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 8$)，表示测试用例的总数。对于每个测试用例，第一行包含 $n$ ($1 \le n \le 1000$)。接下来的 $n$ 行描述栅栏，每行包含五个空格分隔的整数 $x_{1i}, y_{1i}, x_{2i}, y_{2i}$ 和 $p_i$，其中 $|x_{1i}|, |y_{1i}|, |x_{2i}|, |y_{2i}| \le 10^9$ 且 $1 \le p_i \le 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示 John 所需的最小花费。

样例

输入 1

2
5
0 0 0 1 1
0 0 1 0 1
0 1 1 1 1
1 0 1 1 1
1 0 0 1 100
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: 106
Case #2: 22