Mr.Panda 正在玩一款名为《Watcher of Samsara》的游戏，这是一款由中国工作室开发的著名塔防游戏。在游戏开始时，每位玩家都可以从游戏系统随机生成的英雄池中任意选择他们的第一个英雄。在所有英雄中，Mr.Panda 总是选择名为 Leshrac 的英雄，因为该角色的终极技能是“脉冲新星”（Pulse Nova）。

脉冲新星每秒在 Leshrac 周围产生一波破坏性能量，以伤害所有附近的敌方单位。这个强大的技能启发 Mr.Panda 提出了一个几何问题。

在二维平面上有 $n$ 条直线，其中第 $i$ 条直线经过两个整数点 $P_i$ 和 $Q_i$。你需要在这个平面上放置一个半径恰好为 $R$ 的圆。对于每一条给定的直线，该直线可能有一部分线段位于圆内。请找到该圆的一个位置，使得所有位于圆内的线段部分的总长度最大。

输入格式

第一行输入包含测试用例的数量 $T$ ($1 \le T \le 100$)。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ ($1 \le n \le 50$) 和 $R$ ($1 \le R \le 3000$)，分别表示直线的数量和圆的半径。

接下来的 $n$ 行，每行包含四个整数。在第 $i$ 行中，前两个整数表示点 $P_i$ 的二维坐标，后两个整数表示点 $Q_i$ 的二维坐标。我们保证 $P_i \neq Q_i$，且每个坐标的绝对值不超过 $1000$。

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

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是位于圆内的最大总长度。如果你的答案与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则被视为正确。

样例

输入 1

3
2 2
1 1 1 2
1 1 2 1
4 3
0 0 0 1
2 0 0 1
0 0 1 0
0 2 1 2
5 4
1 3 -2 3
0 0 4 0
0 1 -1 2
-3 1 2 -1
1 3 2 -3

输出 1

Case #1: 8.0000000000
Case #2: 23.3137084990
Case #3: 38.0402955628

说明

对于第一个样例，你可以将圆心放置在 $(1, 1)$，这样圆内的总长度为 $8$。

对于第二个样例，你可以将圆心放置在 $(0, 1)$，这样圆内的总长度为 $12 + 8\sqrt{2}$。