Problem N
Visitors Train

An aviary or a flight cage is a big cage for birds. An usual ZOO aviary typically measures tens of meters in diameter. In the aviaries, the birds can fly around and live in conditions imitating the conditions in the wild as closely as possible. At least in theory. There is one main big and spectacular aviary in the ZOO and some other less important ones.

The ZOO is planning to build a short straight electric train track to help visitors to move easily from one part of the ZOO to another. It has to be decided which of the free areas of the ZOO will the track run through. The director had noticed during his trips to other ZOOs that the visitors are more happy when they can take more photos of important ZOO structures. Now he wants to measure the quality of the planned railway by this parameter. The most important structure in the vicinity of the track will be the main aviary. The director worries that the main aviary might be obscured by the less important aviaries along the track and the visitors might be less happy. Help the director to assess the quality of the planned track.

Figure 1: Sample Input 1

You are given the coordinates of all aviaries. Also, you are given the coordinates of the start and the end of the planned railway track. Find the total length of the segments on the track from which the main aviary is visible and is not obscured, even not partially, by any other aviary. We suppose that the visitors can look out from the train in any direction.

Input

The first line of input contains the number of test cases $T$ ($1 \leq T \leq 16$). The descriptions of the test cases follow:

The first line contains number $N$ ($1 \leq N \leq 100$) of the aviaries. Next line contains the coordinates of the planned railway track in the format $x_1$ $y_1$ $x_2$ $y_2$ where $[x_1, y_1]$ and $[x_2, y_2]$ are the coordinates of the start and the end of the track. The track is considered to be infinitely thin in this representation. Next, there are $N$ lines specifying the aviaries, each aviary is represented as a rectangle with nonzero area. Each of these lines specifies the coordinates of an aviary in the form $x_1$ $y_1$ $x_2$ $y_2$ $x_3$ $y_3$ $x_4$ $y_4$, where $[x_1, y_1]$, $[x_2, y_2]$, $[x_3, y_3]$, and $[x_4, y_4]$ are the coordinates of the aviary corners. The corners are presented in clockwise or anti-clockwise order. The main aviary is listed first. All coordinates are integers, their absolute value is less than $10\, 000$. You may assume that no aviary intersects or touches the track or another aviary.

Output

For each test case print on a separate line the total length $L$ of all segments of the planned track from which the main aviary is visible and it is not obscured, even not partially, by any other aviary. Your answer should not differ from the correct answer by more than $10^{-4}$.

As shown in the third sample input, the main aviary is not considered obscured if only its corners/edges are hidden.

4
5
3 1 17 15
6 14 4 17 7 19 9 16
2 12 1 13 2 14 3 13
8 9 8 12 9 12 9 9
12 14 10 18 12 19 14 15
12 6 18 9 19 7 13 4
1
0 0 0 2
4 -1 4 1 5 1 5 -1
2
0 0 0 1
4 0 4 2 5 2 5 0
2 0 3 0 3 -1 2 -1
2
0 0 0 1
4 0 4 2 5 2 5 0
2 0 3 0 3 1 2 1

7.07105
2.00
1.00
0.00