1115: 骑士跳棋

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：1008 Solved：584

Description

背景

Somurov先生是一位出色的国际象棋棋手，他断言，除了他之外，没有人能如此迅速地将骑士从一个位置移动到另一个位置。你能打败他吗？

你的任务是编写一个程序来计算骑士从一个点到另一个点所需的最小移动次数，这样你就有机会比Somurov更快。对于不熟悉国际象棋的人来说，可能的骑士招式如图所示。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

第一行一个数字T，表示有T组测试用例

每组测试用例包含三行整数。

第一行指定了棋盘一侧的长度L（4<=L<=300）。整个棋盘的大小为L*L。

第二行包含2个整数Sx,Sy，指定骑士在棋盘上开始位置。整数由一个空格分隔。

第三行包含2个整数Ex,Ey，指定骑士在棋盘上结束位置。整数由一个空格分隔。

0<=Sx,Sy,Ex,Ey<L

您可以假设这些位置是该场景中棋盘上的有效位置。

Output

对于输入的每组测试用例，输出一行，包含一个整数表示从起点移动到终点所需的骑士移动的最少数量。

如果起点和终点相等，则距离为零。如果对到达不了，输出-1


Sample Input Copy 

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

Sample Output Copy 

5
28
0

Source/Category