暂无测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

D. Come Together

时间限制：2 seconds

空间限制：256 megabytes

原题链接：https://codeforces.com/gym/451807/problem/D

题目描述

Bob和Carol和Alice一起玩了一整天，但现在是时候回家了。爱丽丝、鲍勃和卡罗尔分别住在一个无限的二维网格中的\(A\)、\(B\)和\(C\)单元格。现在，他们都在\(A\)单元格中。

如果Bob（或Carol）在某个单元格中，他（她）可以移动到邻近的一个单元格中。如果两个单元格共享一个边，则称为相邻。例如，单元格\((3, 5)\)有四个相邻的单元格：\((2, 5)\)、\((4, 5)\)、\((3, 6)\)和\((3, 4)\)。

Bob想回到\(B\)单元，Carol想回到\(C\)单元。他们都想沿着最短的路径走，即沿着由尽可能少的单元格组成的路径走。但他们也想一起走。

如果Bob和Carol各自使用一条最短路径回家，那么他们一起走的最大可能的单元数是多少？

输入

第一行包含单个整数\(t\)（\(1 \le t \le 10^4\)）--测试案例的数量。

每个测试案例的第一行包含两个整数\(x_A\)和\(y_A\)（\(1 \le x_A, y_A \le 10^8\)）--单元格\(A\)的位置，Bob和Carol现在都在这里。

第二行包含两个整数\(x_B\)和\(y_B\)（\(1 \le x_B, y_B \le 10^8\)）--单元格\(B\)（Bob的房子）的位置。

第三行包含两个整数\(x_C\)和\(y_C\)（\(1 \le x_C, y_C \le 10^8\)）--单元格\(C\)（Carol的房子）的位置。

对输入的额外约束：每个测试案例中的单元格\(A\)、\(B\)和\(C\)是成对不同的。

输出

对于每个测试案例，打印单个整数--如果Bob和Carol各自沿着一条最短路径回家，他们可以一起走的最大单元格数。

样例

输入样例

3
3 1
1 3
6 4
5 2
2 2
7 2
1 1
4 3
5 5

输出样例

3
1
6

样例解释

在所有图片中，红色表示只属于Bob路径的细胞，浅蓝色--只属于Carol路径的细胞，而深蓝色--属于两条路径的细胞。

第一个测试案例的最佳路线之一如下所示：

第二个测试案例的最佳答案如下所示：

第三个测试案例的最佳答案之一如下所示：

Bob的路线包含\(6\)单元格，Carol的路线包含\(9\)单元格，他们将一起访问\(6\)单元格。