干将是豫州的朋友，但为曹操效力。一天，干将造访豫州军队，想在午夜从豫州军队中窃取一些东西。豫州邀请他留宿一晚，并布置了守卫。

干将看到豫州军队中有 $N$ 个堡垒，编号为 $0, 1, 2, \dots, n-1$。守卫连接着相邻的堡垒，包括 $(0, 1), (1, 2), \dots, (n-2, n-1), (n-1, 0)$，形成了一个简单多边形。干将身处堡垒 $0$，只允许沿直线向编号更高的堡垒走。他不允许进入多边形内部，甚至不允许经过其他顶点，但他可以沿着多边形的边走，例如从堡垒 $2$ 走到堡垒 $3$。当干将到达一个堡垒时，他可以窃取价值为 $V_i$ 的信件。但行走会让他不开心，每走一个单位长度，他就会获得 $1$ 个单位的不开心值。干将可以随时结束任务并骑马回到曹操那里。

图 1：第 3 个样例

干将希望使信件的总价值尽可能大，同时使不开心值尽可能小。因此，他的目标是使信件总价值减去总不开心值尽可能大。请帮助干将实现这一目标。

输入格式

第一行输入包含测试用例的数量 $T(1 \le T \le 10)$。接下来是 $T$ 个测试用例。每个测试用例以一个整数 $N(1 \le N \le 1000)$ 开始。接下来的 $N$ 行，每行包含 $3$ 个保留 $4$ 位小数的浮点数 $x_i, y_i(-10^5 \le x_i, y_i \le 10^5)$ 和 $V_i(0 \le V_i \le 10^5)$，其中 $(x_i, y_i)$ 表示堡垒 $i$ 的坐标，$V_i$ 表示堡垒 $i$ 中信件的价值。

输出格式

对于每个测试用例，输出一行包含 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是信件总价值减去总不开心值的最大值。如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-4}$ 以内，则被视为正确。

样例

输入 1

3
4
0.0000 0.0000 0.0000
1.0000 0.0000 0.5000
1.0000 1.0000 2.0000
0.0000 1.0000 0.5000
5
0.0000 0.0000 0.0000
1.0000 1.0000 0.5000
2.0000 0.0000 2.0000
2.0000 2.0000 3.0000
0.0000 2.0000 0.0000
11
0.0000 0.0000 100.0000
1.0000 1.0000 100.0000
2.0000 0.0000 100.0000
2.0000 2.0000 100.0000
3.0000 2.0000 100.0000
3.0000 -2.0000 100.0000
1.0000 0.0000 100.0000
1.0000 -3.0000 100.0000
4.0000 -3.0000 100.0000
4.0000 4.0000 100.0000
0.0000 4.0000 100.0000

输出 1

Case #1: 0.5000
Case #2: 1.0000
Case #3: 1070.3431