5503: 暑期营第二天D. Knight Moves

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

编写一个程序,计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数,骑士一步可以移动到的位置由下图给出,

Input

第一行给出骑士的数量n。
在接下来的 3n.行中,每3行描述了一个骑士。其中
       第一行一个整数L工表示棋盘的大小,整个棋盘大小为L×L ;
       第二行和第三行分别包含一对整数(x,y),表示骑士的起始点和终点。假设对于每一个骑士,起始点和终点均合理

Output

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

Sample Input Copy


 3
 8
 0 0
 7 0
 1 0 0
 0
 30 50
 1 0
 1 1
 1 1

Sample Output Copy


 5
 2 8
 6

HINT

对于 100%的数据,有4<=L<= 300,保证0 <=x,y<=L-1