Come Together
Contest: Educational Codeforces Round 151 (Rated for Div. 2)
Difficulty rating: 900
Tags: geometry, implementation, math

Bob and Carol hanged out with Alice the whole day, but now it's time to go home. Alice, Bob and Carol live on an infinite 2D grid in cells $$$A$$$, $$$B$$$, and $$$C$$$ respectively. Right now, all of them are in cell $$$A$$$.

If Bob (or Carol) is in some cell, he (she) can move to one of the neighboring cells. Two cells are called neighboring if they share a side. For example, the cell $$$(3, 5)$$$ has four neighboring cells: $$$(2, 5)$$$, $$$(4, 5)$$$, $$$(3, 6)$$$ and $$$(3, 4)$$$.

Bob wants to return to the cell $$$B$$$, Carol — to the cell $$$C$$$. Both of them want to go along the shortest path, i. e. along the path that consists of the minimum possible number of cells. But they would like to walk together as well.

What is the maximum possible number of cells that Bob and Carol can walk together if each of them walks home using one of the shortest paths?

Input format:
The first line contains the single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$x_A$$$ and $$$y_A$$$ ($$$1 \le x_A, y_A \le 10^8$$$) — the position of cell $$$A$$$, where both Bob and Carol are right now.

The second line contains two integers $$$x_B$$$ and $$$y_B$$$ ($$$1 \le x_B, y_B \le 10^8$$$) — the position of cell $$$B$$$ (Bob's house).

The third line contains two integers $$$x_C$$$ and $$$y_C$$$ ($$$1 \le x_C, y_C \le 10^8$$$) — the position of cell $$$C$$$ (Carol's house).

Additional constraint on the input: the cells $$$A$$$, $$$B$$$, and $$$C$$$ are pairwise distinct in each test case.

Output format:
For each test case, print the single integer — the maximum number of cells Bob and Carol can walk together if each of them goes home along one of the shortest paths.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In all pictures, red color denotes cells belonging only to Bob's path, light blue color — cells belonging only to Carol's path, and dark blue color — cells belonging to both paths.

One of the optimal routes for the first test case is shown below:

The optimal answer for the second test case is shown below:

One of the optimal answers for the third test case is shown below:

Example input:
3
3 1
1 3
6 4
5 2
2 2
7 2
1 1
4 3
5 5

Example output:
3
1
6

Editorial:
Let $$$d(P_1, P_2)$$$ be the Manhattan distance between points $$$P_1 = (x_1, y_1)$$$ and $$$P_2 = (x_2, y_2)$$$. Then $$$d(P_1, P_2) = |x_1 - x_2| + |y_1 - y_2|$$$.
Note that if you are going from $$$A$$$ to $$$B$$$ (or to $$$C$$$) along the shortest path, the Manhattan distance will be decreasing with each move. So Bob and Carol can walk together as along as they find the next cell that is closer to both $$$B$$$ and $$$C$$$.
Now note that if they are in the bounding box of cells $$$B$$$ and $$$C$$$ then there are no such "next cell", since $$$d(X, B) + d(X, C)$$$ is constant and equal to $$$d(A, B)$$$ if $$$X$$$ is in the bounding box. In other words, Bob and Carol can walk together until they reach some cell $$$X$$$ inside the bounding box, where they split up.
Finally, let's look at the total distance they will walk: from one side it's $$$d(A, B) + d(A, C)$$$. But from the other side it's $$$2 \cdot d(A, X) + d(X, B) + d(X, C)$$$.
So, $$$$$$d(A, X) = \frac{d(A, B) + d(A, C) - (d(X, B) + d(X, C))}{2}$$$$$$ But since $$$d(X, B) + d(X, C) = d(B, C)$$$ whichever $$$X$$$ is chosen we can calculate answer as $$$$$$\frac{d(A, B) + d(A, C) - d(B, C)}{2} + 1$$$$$$ where $$$+1$$$ is because we are talking about cells $$$A$$$, $$$B$$$ and $$$C$$$ and not just points.