Problem Description

On a 2D plane, you are given two line segments $AB$ and $CD$, which are parallel to the $x$-axis and the $y$-axis respectively.

You may choose one segment and translate it in any direction parallel to the coordinate axes (up, down, left, or right) by any distance. This is called one operation.

What is the minimum number of operations needed to make the two segments intersect?

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

• One line contains eight positive integers $x_A,y_A,x_B,y_B,x_C,y_C,x_D,y_D$, representing the coordinates of $A,B,C,D$.

Output Format

For each test case:

• Output one integer per line, the minimum number of operations.

3
1 1 2 1 1 1 1 2
1 1 2 1 1 2 1 3
2 1 3 1 1 2 1 3

0
1
2

Hint

[Sample 1 Explanation]

• For the first test case, the two segments already intersect, so no operation is needed.
• For the second test case, one feasible plan is: translate segment $AB$ upward by $1$ unit.
• For the third test case, one feasible plan is: translate segment $AB$ upward by $1$ unit, then translate segment $CD$ rightward by $1$ unit.

[Constraints]

Let $M=\max(x_A,y_A,x_B,y_B,x_C,y_C,x_D,y_D)$.

For $100\%$ of the testdata, $1\le T\le 10^5$, $1\le M\le 10^{9}$, $x_A<x_B$, $x_C=x_D$, $y_A=y_B$, $y_C<y_D$.

Translated by ChatGPT 5