无限二维网格上有三个单元格,标记为 $$$A$$$、$$$B$$$ 和 $$$F$$$。求从 $$$A$$$ 到 $$$B$$$ 的最短路径的长度,如果:
- 一次移动,你可以到达共享一侧的四个相邻单元格中的任何一个;
- 禁止访问单元格$$$F$$$(它是一个障碍)。
输入
第一行包含一个整数 $$$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$$$对应行号(见下图)。
输出
输出 $$$t$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 测试用例的答案:如果不允许访问单元格 $$$F$$$,则从单元格 $$$A$$$ 到单元格 $$$B$$$ 的最短路径的长度。
示例
输入 #1
7 1 1 3 3 2 2 2 5 2 1 2 3 1000 42 1000 1 1000 1000 1 10 3 10 2 10 3 8 7 8 3 7 2 1 4 1 1 1 1 344 1 10 1 1
输出 #1
4 6 41 4 4 2 334
注意
第一个测试用例的可能最短路径示例。
第二个测试用例的可能最短路径示例。