Little T is taking a physics lab course this semester. To successfully complete the next experiment, he plans to preview the experiment content beforehand.

The experiment takes place on a 2D plane. An infinitely long straight rail is placed on the plane, and a laser emitter of length $L$ is placed on the rail. The laser emitter emits a laser beam of width $L$ perpendicular to the rail on both sides.

There are also $n$ baffles placed on the plane. Each baffle can be considered a line segment. None of the baffles are in contact with the straight rail, and the angle between each baffle and the straight rail does not exceed $85^\circ$. No two baffles are in contact with each other. The laser beam cannot penetrate these baffles; it is absorbed by them and is not reflected.

Little T wants to determine a position for the laser emitter such that the sum of the lengths of the baffles illuminated by the laser beam is maximized. You need to help Little T calculate this maximum value.

Input

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

The first line is an integer $n$, representing the number of baffles.

The next $n$ lines each contain four integers $x_1, y_1, x_2, y_2$, representing the two endpoints of a baffle as $(x_1, y_1)$ and $(x_2, y_2)$. It is guaranteed that $(x_1, y_1) \neq (x_2, y_2)$.

The $(n+2)$-th line contains five integers $x_1, y_1, x_2, y_2, L$, representing that the straight rail passes through points $(x_1, y_1)$ and $(x_2, y_2)$, and the length of the laser emitter is $L$. It is also guaranteed that $(x_1, y_1) \neq (x_2, y_2)$.

Output

For each test case, output a single line containing a real number, representing the maximum sum of the lengths of the baffles that can be illuminated by the laser beam. The relative error must not exceed $10^{-6}$.

That is, if the output result is $a$ and the standard answer is $b$, the result is considered correct if $\frac{|a-b|}{\max(1, b)} \leq 10^{-6}$.

Examples

Input 1

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

Output 1

3.000000000000000
3.118033988749895
4.251303782246768

Note

• $T \leq 100$
• $1 \leq n \leq 10^4$
• $1 \leq L \leq 2 \times 10^9$
• The absolute value of all coordinates does not exceed $10^9$.

Subtask 1 (40 points): $1 \leq n \leq 100$ and the absolute value of all coordinates does not exceed $10^4$.

Subtask 2 (40 points): The absolute value of all coordinates does not exceed $10^6$.

Subtask 3 (20 points): No additional restrictions.