Pulse Nova

Mr.Panda is playing Watcher of Samsara, a tower defense game. At the start of the game, every player can freely pick their first hero from a hero pool that the game system generates at random. Mr.Panda always picks Leshrac, because of the character's ultimate skill, Pulse Nova.

Pulse Nova sends out a wave of damaging energy around Leshrac once per second, hitting every nearby enemy unit. This skill gave Mr.Panda an idea for a geometry problem.

There are $n$ straight lines on the 2D plane. The $i$-th line passes through two integer points $P_i$ and $Q_i$. Place a circle with radius exactly $R$ on the plane. For each given line, a segment of that line may lie inside the circle. Find a position for the circle that maximizes the total length of all these segments inside the circle.

The first line contains $T$ ($1 \le T \le 100$), the number of test cases. Each test case follows.

The first line of each test case contains two integers $n$ ($1 \le n \le 50$) and $R$ ($1 \le R \le 3000$), the number of lines and the radius of the circle.

The next $n$ lines each contain four integers. On the $i$-th of these lines, the first two integers are the coordinates of $P_i$, and the last two are the coordinates of $Q_i$. $P_i \ne Q_i$, and the absolute value of every coordinate is at most 1000.

The sum of $n$ over all test cases is at most 100.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1, and $y$ is the maximum total length inside the circle. An answer is correct if its absolute or relative error is within $10^{-6}$.

In the first sample, placing the center at $(1, 1)$ gives a total length of 8 inside the circle.

In the second sample, placing the center at $(0, 1)$ gives a total length of $12 + 8\sqrt{2}$ inside the circle.