题目

给定一个n×n的棋盘，以及一个开始位置和终点位置。 棋盘的横纵坐标范围都是0～n－1。 将一个国际象棋中的骑士放置在开始位置上，请问将它移动至终点位置至少需要走多少步。 一个骑士在棋盘上可行的移动方式如下图所示：

输入格式

第一行包含整数T，表示共有T组测试数据。 每组测试数据第一行包含整数n，表示棋盘大小。 第二行包含两个整数x,y用来表示骑士的开始位置坐标(x,y)。 第三行包含两个整数x,y用来表示骑士的终点位置坐标(x,y)。

输出格式

每组数据输出一个整数，表示骑士所需移动的最少步数，每个结果占一行。

样例

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

5
28
0

提示

对于 100% 的数据，有 4≤n≤300，保证 0≤x,y≤n−1。

来源

一本通在线评测