Knight Moves

题目描述

在一个 L×L 的棋盘上有一个骑士（马）。骑士可以朝棋盘的八个方向走马字步（“日”字）。给定骑士的起始位置和目标位置，问从起始位置到目标位置最少需要走多少步。

输入

首先输入一个整数 n（1 ≤ n ≤ 50），表示测试样例的个数。接下来每个测试样例有三行：

• 第一行是棋盘的大小 L（4 ≤ L ≤ 300）；
• 第二行是马的起始位置坐标，包含两个整数 x1、y1（0 ≤ x1, y1 ≤ L-1）；
• 第三行是马的目标位置坐标，包含两个整数 x2、y2（0 ≤ x2, y2 ≤ L-1）。

输出

对每个测试样例，输出马从起始位置走到目标位置的最小步数，每个结果占一行。当起始位置和目标位置相同时输出 0。

样例输入

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

样例输出

5
28
0