Problem E
Real Manhattan Distance

The city of Manhattan is well known for its regular arrangement of numbered streets and avenues (streets run east-west and avenues run north-south), which can be modeled by a grid superimposed on the $x\textrm{-}y$ plane with vertical and horizontal lines at integer values of $x~ \textrm{and}~ y$. The Manhattan distance (or taxicab distance) between two points, $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$, is given by

(here we assume integer coordinates, although Manhattan distance can also be applied more generally). This captures the idea that the shortest distance between two intersections in Manhattan (for a vehicle like a car or truck that is restricted to travelling along streets and avenues) is the sum of the differences between the street numbers and the avenue numbers (in absolute value for each).

But this simple model ignores one of the most famous features of Manhattan — Broadway! Known as a global center for live theater, especially musical theater, Broadway (which is a road) is also significant because, in a certain part of Manhattan, it cuts at an angle across the regular grid of streets and avenues. If a vehicle can travel along Broadway for at least part of its journey, this potentially reduces the shortest distance between its starting point and its destination relative to a trip along only streets and avenues.

We will model Broadway by adding a single non-vertical and non-horizontal line segment to the grid described above. This line segment has endpoints with integer coordinates, $(\mathit{bx}_1, \mathit{by}_1)$ and $(\mathit{bx}_2, \mathit{by}_2)$, and each point where it intersects a vertical or horizontal grid line creates a new intersection (unless one exists there already).

Now what is the shortest distance from $(x_1, y_1)$ to $(x_2, y_2)$ for a vehicle that can travel along any street or avenue, and can also travel along Broadway? Note that all streets, all avenues, and Broadway are bi-directional.

Figure 1: Shortest route for the first test case in the sample input

Input

The first line of input contains an integer, $n$, the number of test cases $(1 \leq n \leq 100)$. This is followed by $n$ lines, each of which contains $8$ space-separated integers, $\mathit{bx}_1$, $\mathit{by}_1$, $\mathit{bx}_2$, $\mathit{by}_2$, $x_1$, $y_1$, $x_2$, $y_2$, where $(\mathit{bx}_1, \mathit{by}_1)$ and $(\mathit{bx}_2, \mathit{by}_2)$ are the endpoints of Broadway, $(x_1, y_1)$ is the starting intersection of a trip through Manhattan, and $(x_2, y_2)$ is the destination intersection. Each coordinate is in the interval $[1,50]$. It is guaranteed that $\mathit{bx}_1 \neq \mathit{bx}_2$, $\mathit{by}_1 \neq \mathit{by}_2$, and $(x_1, y_1) \neq (x_2, y_2)$.

Output

For each test case, output a single line containing the shortest distance between $(x_1, y_1)$ and $(x_2, y_2)$ as described above. An answer will be considered correct if it is within $10^{-6}$ of the official answer.

2
5 10 13 14 9 8 11 16
5 10 13 14 9 8 12 7

9.23606797749979
4.0