在火星附近，一个与我们极其相似的遥远星系中，帝国军队与反抗军之间正在进行一场殊死搏斗。反抗军拥有 $N$ 艘飞船，我们可以将其视为空间中的点 $(x_i, y_i, z_i)$。每艘飞船都配有一个功率为 $p_i$ 的接收器。反抗军需要能够从中央巡洋舰向所有飞船发送信息，但由于资金紧张，他们无法负担功率过大的发射器。

如果巡洋舰放置在 $(x, y, z)$，而其中一艘飞船位于 $(x_i, y_i, z_i)$ 且接收器功率为 $p_i$，那么巡洋舰发射器所需的功率至少为：

(|x_i - x| + |y_i - y| + |z_i - z|) / p_i

你的任务是找到巡洋舰的最佳位置，使得其发射器所需的功率最小，并输出该功率值。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 组测试用例。

每个测试用例的第一行包含一个整数 $N$，表示飞船的数量。

接下来的 $N$ 行，每行包含四个整数 $x_i, y_i, z_i$ 和 $p_i$，用空格分隔。这些是第 $i$ 艘飞船的坐标及其接收器的功率。同一坐标处可能存在多艘飞船。

输出格式

对于每个测试用例，输出：

Case #X: Y

其中 $X$ 是测试用例的编号，$Y$ 是能够覆盖所有舰队飞船所需的最小功率。相对误差或绝对误差不超过 $10^{-6}$ 的答案将被视为正确。

数据范围

$1 \le T \le 10$

$0 \le x_i, y_i, z_i \le 10^6$

$1 \le p_i \le 10^6$

小数据集（测试集 1 - 可见；10 分）

$1 \le N \le 10$

大数据集（测试集 2 - 隐藏；20 分）

$1 \le N \le 1000$

样例

样例输入 1

3
4
0 0 0 1
1 2 0 1
3 4 0 1
2 1 0 1
1
1 1 1 1
3
1 0 0 1
2 1 1 4
3 2 3 2

样例输出 1

Case #1: 3.50000000
Case #2: 0.00000000
Case #3: 2.33333333

说明

在第一个测试用例中，四艘飞船的坐标分别为 $(0, 0, 0), (1, 2, 0), (3, 4, 0), (2, 1, 0)$，功率均为 $1$。我们可以将功率为 $3.5$ 的巡洋舰放置在坐标 $(1.5, 2, 0)$ 处，这样它就能覆盖所有飞船。

在第二个测试用例中，我们可以将巡洋舰直接放置在飞船所在的位置，此时发射器功率为 $0$。