Today, The First Grand Tournament of Automated Driving has officially commenced!

The experiment field of this tournament is a rectangular region on a 2-dimensional plane, with axes parallel to the coordinate axes. The bottom-left corner of the field is at coordinate while the top-right corner is at coordinate . There are two segments and lying strictly inside the rectangle. The two segments may share common points. There is also a car inside the rectangle, which can be regarded as a point.
A subtask of this tournament requires that the distances between the car and the two segments must be equal all the time during the movement. The distance between a point and a segment is defined as the minimum Euclidean distance from to any point on .

Please write a program to find the area of valid positions of the car.

The input contains multiple cases. The first line of the input contains a single integer ), indicating the number of test cases.

For each case, the first line of the input contains four integers   , denoting the coordinates of the bottom-left and the top-right corners of the rectangle. Each of the next two lines contains four integers , denoting a segment that connects  and , where  and .

For each case, it is guaranteed that the two endpoints of each segment do not coincide.

For each test case, print a single line containing a single real number, the area of valid positions of the car. Your answer will be considered correct if the absolute or relative error does not exceed .

Formally, if your answer is a and the jury's answer is b, then your answer will be considered correct if and only if .

2
0 0 3 3
1 1 1 2
2 1 2 2
0 0 3 3
1 1 1 2
1 2 2 2

0.000000000000000
1.000000000000000