J. Computational Intelligence
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given two straight line segments on a two-dimensional Cartesian plane, you need to pick a point uniformly at random on each of them and calculate the expected Euclidean distance between the two picked points.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) indicating the number of test cases. For each test case:

The first line contains four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ ($$$-10^3 \le x_1, y_1, x_2, y_2 \le 10^3$$$) indicating that the two endpoints of the first segment are $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.

The second line contains four integers $$$x_3$$$, $$$y_3$$$, $$$x_4$$$ and $$$y_4$$$ ($$$-10^3 \le x_3, y_3, x_4, y_4 \le 10^3$$$) indicating that the two endpoints of the second segment are $$$(x_3, y_3)$$$ and $$$(x_4, y_4)$$$.

It is guaranteed that the two segments both have positive lengths.

Output

For each test case, output one line containing one number indicating the expected distance between the two randomly picked points.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$. Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$, your output is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$$$.

Example
Input
3
0 0 1 0
0 0 1 0
0 0 1 0
0 0 0 1
0 0 1 0
0 1 1 1
Output
0.333333333333333333
0.765195716464212691
1.076635732895178009
Note

Thanks to "Computational Intelligence", we can know that:

For the first sample case, the expected distance is $$$$$$\int_{0}^{1} \int_{0}^{1} |x_0 - x_1| \,\mathrm{d}x_0 \,\mathrm{d}x_1 = \frac{1}{3} \approx 0.333333333333333333;$$$$$$

For the second sample case, the expected distance is $$$$$$\int_{0}^{1} \int_{0}^{1} \sqrt{x^2+y^2} \,\mathrm{d}x \,\mathrm{d}y = \frac{\sqrt{2}+\ln(1+\sqrt{2})}{3} \approx 0.765195716464212691;$$$$$$

For the third sample case, the expected distance is $$$$$$\int_{0}^{1} \int_{0}^{1} \sqrt{(x_0-x_1)^2+1} \,\mathrm{d}x_0 \,\mathrm{d}x_1 = \frac{2-\sqrt{2}+3\ln(1+\sqrt{2})}{3} \approx 1.076635732895178009.$$$$$$