鲍勃和卡罗尔和爱丽丝出去玩了一整天,但现在该回家了。 Alice、Bob 和 Carol 生活在一个无限的二维网格中,分别位于 $$$A$$$、$$$B$$$ 和 $$$C$$$ 单元格中。现在,它们都在单元格 $$$A$$$ 中。
如果鲍勃(或卡罗尔)在某个单元格中,他(她)可以移动到相邻单元格之一。如果两个单元共享一侧,则称为相邻单元。例如,单元格 $$$(3, 5)$$$ 有四个相邻单元格:$$$(2, 5)$$$、$$$(4, 5)$$$、$$$(3, 6)$$$ 和 $$$(3, 4)$$$。
Bob 想要返回单元格 $$$B$$$,Carol 想要返回单元格 $$$C$$$。他们都想走最短的路径,即。 e.沿着由尽可能少的单元组成的路径。但他们也想一起走。
如果鲍勃和卡罗尔各自使用最短路径之一步行回家,那么他们最多可以一起走多少个单元格?
输入
第一行包含单个整数 $$$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$$$(鲍勃的房子)的位置。
第三行包含两个整数 $$$x_C$$$ 和 $$$y_C$$$ ($$$1 \le x_C, y_C \le 10^8$$$) - 单元格 $$$C$$$(卡罗尔的房子)的位置。
输入的附加约束:单元格 $$$A$$$、$$$B$$$ 和 $$$C$$$ 在每个测试用例中都是成对不同的。
输出
对于每个测试用例,打印单个整数 - 如果鲍勃和卡罗尔各自沿着最短路径之一回家,则鲍勃和卡罗尔可以一起行走的最大单元格数。
示例
输入 #1
3 3 1 1 3 6 4 5 2 2 2 7 2 1 1 4 3 5 5
输出 #1
3 1 6
注意
在所有图片中,红色表示仅属于 Bob 路径的单元格,浅蓝色表示仅属于 Carol 路径的单元格,深蓝色表示属于两条路径的单元格。
第一个测试用例的最佳路线之一如下所示:
第二个测试用例的最佳答案如下所示:
第三个测试用例的最佳答案之一如下所示: