Description

Original Source: POJ 1915

Write a program to calculate the minimum number of moves a knight requires to travel from one square to another on a chessboard. The positions a knight can move to in one step are illustrated in the figure below.

Input Format

The first line provides the number of knights, $n$.
In the following $3n$ lines, every $3$ lines describe one knight. Specifically,

• The first line contains an integer $L$ indicating the size of the chessboard, which is $L\times L$;
• The second and third lines each contain a pair of integers $(x, y)$, representing the starting and ending positions of the knight. It is assumed that for each knight, the starting and ending positions are valid.

Output Format

For each knight, output one line with an integer representing the minimum number of moves required. If the starting and ending positions are the same, output $0$.

Sample 1

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

5
28
0

Data Range and Hint

For $100\%$ of the data, $4\le L\le 300$, and it is guaranteed that $0\le x,y\le L-1$.