时间限制：1秒　　内存限制：256M

---

【题目描述】

　　所谓骑士游历问题，是指给出一个 \(n×n\) 的国际象棋棋盘，马（也称为骑士）从指定的格子出发（出发格子），以跳马规则（横一步竖两步或横两步竖一步），跳到另一个格子（目标格子）最少需要跳多少次。

　　关于跳马规则，每次可向八个方向之一跳，如下图所示。

【输入格式】

　　第一行为数据组数 \(T\)。每组数据的第一行是整数 \(n\)，表示棋盘的大小，从下到上的行号为 \((0..n-1)\)，从左到右为列号为 \((0..n-1)\)，接下来的两行分别为出发格子行列号和目标格子的行列号。

【输出格式】

　　每组数据输出一行一个数据，表示从出发格子到目标格子，骑士需要跳的最少次数。如果不能走到目标格子，请输出"None"。

【输入输出样例】

　Input

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

　Output

5
28
0

【数据限制】

　　对于 \(100\%\) 的数据，\(T≤10，1≤n≤300\)。

【来源】

　　Mr.he