题目描述

写程序，计算骑士从一个位置移动到另一个位置所需的最少移动次数。骑士移动的规则如下图所示

输入格式

输入的第 $1$ 行为测试用例的个数 $N$ 。每个测试用例都包含 $3$ 行。

第1行表示棋盘的长度 $L （4≤L ≤300）$，棋盘的大小为 $L ×L$；

第2行和第3行包含一对{$0$,…,$L -1$}×{$0$,…,$L -1$}的整数，表示骑士在棋盘上的起始位置和结束位置。

假设这些位置是该棋盘上的有效位置。

输出格式

对于每个测试用例，都单行输出骑士从起点移动到终点所需的最少移动次数。如果起点和终点相等，则移动次数为零。

样例

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

5
28
0

来源

POJ1915