象棋--马

Time Limit: 2000 ms

Memory Limit: 65535 ms

Description

中国象棋中的“马”是一个让人着迷的棋子,它走位风骚,杀人于无形之中,象棋高手都对马运用纯熟。众所周知,“马”走“日”子形,现在有一张m*m棋盘,已知“马”的位置,以及想要去的位置,请找出最短的步数完成。

Input

第一行为n(n<=50),表示有n组测试数据 每组测试数据中含5个正整数m(m<1000),x1,y1,x2,y2; 马的起始位置(x1,y1),目标位置(x2,y2);

Output

所需要的最短步数

Sample Input

3
9
1 1
2 3
11
1 1
3 3
12
1 1
3 4

Sample Output

1
4
3

Hint

Source

dreaming3000

提交代码