骑士移动

题目描述:

佳佳是一名出色的棋手，声称没有人能像他那样快速地把骑士从一个位置移到另一个位置。你能打败他吗？

你的任务是编写一个程序，计算一个骑士从一个点移动到另一点所需的最少步数。

对于不熟悉棋的人来说，骑士可以移动的位置由下图所示。

输入格式:

第一行给出骑士的数量n。对于每一个骑士都有3行，第一行一个整数L，表示棋盘的大小（4<=L<=300），整个棋盘大小为(L+1)*(L+1)；

第二行和第三行分别包含一对整数（x,y），表示骑士的起始点和终点。假设，对于每一个骑士起始点和终点均合理。

输出格式:

对每一个骑士输出出一行，一个整数表示需要移动的最少步数。如果起始点和终点相同，则输出0。

样例输入:

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

样例输出:

5
28
0

提示:

题目大意：在0...300的范围的棋盘上，给定起点和终点，按照规定的8种行走方式，求从起点到终点的最少步数。

时间限制: 1000ms
空间限制: 256MB

---