J. Minimum Manhattan Distance
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Recall that on a two-dimensional plane, the Manhattan distance between two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$|x_1-x_2|+|y_1-y_2|$$$. If both coordinates of a point are all integers, then we call this point an integer point.

Given two circles $$$C_1,C_2$$$ on the two-dimensional plane, and guaranteed the $$$x$$$-coordinates of any point in $$$C_1$$$ and any point in $$$C_2$$$ are different, and the $$$y$$$-coordinates of any point in $$$C_1$$$ and any point in $$$C_2$$$ are different.

Each circle is described by two integer points, and the segment connecting the two points represents a diameter of the circle.

Now you need to pick a point $$$(x_0,y_0)$$$ inside or on the $$$C_2$$$ such that minimize the expected value of the Manhattan distance from $$$(x_0,y_0)$$$ to a point inside $$$C_1$$$ , if we choose this point with uniformly probability among all the points with a real number coordinate inside $$$C_1$$$.

Input

The first line contains a single integer $$$t\ (1\le t\le 10^5)$$$ , representing the number of test cases.

Then follow the descriptions of each test case.

The first line contains $$$4$$$ integers $$$x_{1,1},y_{1,1},x_{1,2},y_{1,2}$$$, representing the segment connecting $$$(x_{1,1},y_{1,1})$$$ and $$$(x_{1,2},y_{1,2})$$$ is a diameter of the circle $$$C_1$$$.

The second line contains $$$4$$$ integers $$$x_{2,1},y_{2,1},x_{2,2},y_{2,2}$$$, representing the segment connecting $$$(x_{2,1},y_{2,1})$$$ and $$$(x_{2,2},y_{2,2})$$$ is a diameter of the circle $$$C_2$$$.

All the coordinates input are integers in the range $$$[-10^5, 10^5]$$$ .

Output

For each test case, output a single line with a real number - the minimum expected Manhattan distance. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. That is, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then the solution will be accepted if $$$\frac{|a-b|}{\max (1,|b|)} \leq 10^{-6}$$$ .

Example
Input
1
0 0 2 1
4 5 5 2
Output
4.2639320225