CF1547A.Shortest Path with Obstacle

There are three cells on an infinite 2-dimensional grid, labeled $A$, $B$, and $F$. Find the length of the shortest path from $A$ to $B$ if:

• in one move you can go to any of the four adjacent cells sharing a side;
• visiting the cell $F$ is forbidden (it is an obstacle).

在一个无限的二维网格上有三个格子，标记为 $A$、$B$ 和 $F$。求从 $A$ 到 $B$ 的最短路径长度，要求满足：

• 每次移动可到达上下左右四个相邻（共享一条边）的格子之一；
• 禁止经过格子 $F$（它是一个障碍物）。

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow. Before each test case, there is an empty line.

Each test case contains three lines. The first one contains two integers $x_A, y_A$ ($1 \le x_A, y_A \le 1000$) — coordinates of the start cell $A$. The second one contains two integers $x_B, y_B$ ($1 \le x_B, y_B \le 1000$) — coordinates of the finish cell $B$. The third one contains two integers $x_F, y_F$ ($1 \le x_F, y_F \le 1000$) — coordinates of the forbidden cell $F$. All cells are distinct.

Coordinate $x$ corresponds to the column number and coordinate $y$ corresponds to the row number (see the pictures below).

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 输入中测试用例的数量。随后是 $t$ 个测试用例。每个测试用例之前有一空行。

每个测试用例包含三行。第一行包含两个整数 $x_A, y_A$（$1 \le x_A, y_A \le 1000$）—— 起始格子 $A$ 的坐标；第二行包含两个整数 $x_B, y_B$（$1 \le x_B, y_B \le 1000$）—— 终止格子 $B$ 的坐标；第三行包含两个整数 $x_F, y_F$（$1 \le x_F, y_F \le 1000$）—— 禁止通行格子 $F$ 的坐标。所有格子互不相同。

坐标 $x$ 对应列号，坐标 $y$ 对应行号（参见下方图片）。

Output $t$ lines. The $i$-th line should contain the answer for the $i$-th test case: the length of the shortest path from the cell $A$ to the cell $B$ if the cell $F$ is not allowed to be visited.

输出 $t$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案：即从单元格 $A$ 到单元格 $B$ 的最短路径长度（禁止经过单元格 $F$）。

An example of a possible shortest path for the first test case.

An example of a possible shortest path for the second test case.

第一个测试用例中一条可能的最短路径示例。

第二个测试用例中一条可能的最短路径示例。