It is too easy to calculate the length of a segment in a convex polygon. But now you must calculate the length of a segment in a simple polygon. You are given a simple polygon and a segment, and then you must work out the sum of all the section which is in the polygon.You must notice that a section which is on the side of the polygon will not be considered. For example, in Figure 1, some section of segment PQ is on the side ED of polygon ABCDEF, so the length of segment DQ is the answer of this problem.

The input contains multiple test cases. The first line contains an integer T describing the number of test cases. For each test case: The first line is an integer number n, indicating the number of vertexes of that polygon, then n lines following, each with two integer numbers x and y indicating the coordinate of each vertex. Note that these vertexes are successively given clockwise or anticlockwise for each polygon. The last line of each test case contains four integers. The first two are indicated the coordinate of one end point of the segment, and the last two are indicated the other end point. All the numbers are separated by spaces. All the input integers are within the range of [-1000, 1000].

For each test case, output one line containing a number with 3 digits after decimal point representing the length of a segment in a simple polygon.