杯子宇宙（Universe of Cup）是小青鱼（Little Cyan Fish）居住的地方。宇宙中最大的行星被称为彩虹地球（Rainow-Earth），它是三维欧几里得空间中一个以 $(0, 0, 0)$ 为球心、半径为 $r$ 的球面。

小鲮鱼（Little Cirrhinus Molitorella）在彩虹地球上运营着航空公司。彩虹地球表面上有 $2n$ 个城市（表示为球面上的点）。对于每个 $i = 1, 2, \dots, n$，在第 $2i - 1$ 个城市和第 $2i$ 个城市之间有一条沿着彩虹地球表面最短路径的航线。

图 1：球面两点之间的最短路径（CC BY-SA 4.0，由 Wikimedia Commons 上的 CheCheDaWaff 提供）

小青鱼准备建造一所大学——美德大学（Pretty Kind University）。然而，繁忙的空中交通给小青鱼带来了很大的困扰，他希望将大学建在一个尽可能远离噪音的地方。给定他的容忍度 $k$，小青鱼希望找到最大的 $d$，使得在 $n$ 条航线中，至多有 $k$ 条航线到大学的最短距离严格小于 $d$。

请注意，两点之间的距离是通过测量彩虹地球表面上的最短路径来计算的，这不是三维欧几里得空间中的欧几里得距离。

图 2：P 和 Q 之间的距离是浅蓝色路径的长度，而不是红色线段的长度（CC BY-SA 4.0，由 Wikimedia Commons 上的 PlatypeanArchcow 提供）

输入格式

每个输入文件中包含多个测试用例。输入的第一行包含一个整数 $T$ ($T \ge 1$)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $n$ ($1 \le n \le 100$)、$k$ ($0 \le k < n$) 和 $r$ ($1 \le r \le 100$)，分别表示航线的数量、小青鱼的容忍度以及彩虹地球的半径。

接下来的 $2n$ 行描述所有的城市。其中的第 $i$ 行包含三个整数 $x$、$y$ 和 $z$ ($-100 \le x, y, z \le 100$，$x^2 + y^2 + z^2 > 0$)，表示第 $i$ 个城市的坐标为 $\left( \frac{rx}{\sqrt{x^2+y^2+z^2}}, \frac{ry}{\sqrt{x^2+y^2+z^2}}, \frac{rz}{\sqrt{x^2+y^2+z^2}} \right)$。

保证对于每个 $i = 1, 2, \dots, n$，第 $2i - 1$ 个城市和第 $2i$ 个城市在彩虹地球上既不重合，也不互为对跖点（即不直接相对）。因此，每条航线在彩虹地球表面上的最短路径是唯一确定的。

保证所有测试用例中 $n$ 的总和不超过 $100$。

输出格式

对于每个测试用例，输出一行，包含一个实数，表示 $d$ 的最大值。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。正式地，设你的输出为 $x$，裁判的答案为 $y$，当且仅当 $\frac{|x-y|}{\max(1, |y|)} \le 10^{-6}$ 时，你的输出才会被接受。

样例

输入样例 1

3
1 0 100
0 0 1
0 1 0
2 0 100
1 1 0
1 -1 0
-1 0 1
-1 0 -1
2 1 100
1 1 0
1 -1 0
-1 0 1
-1 0 -1

输出样例 1

235.619449019234
117.809724509617
235.619449019234

说明

对于第一个测试用例，精确答案为 $75\pi$。

对于第二个测试用例，精确答案为 $\frac{75}{2}\pi$。

对于第三个测试用例，精确答案为 $75\pi$。