나이트의 이동

L×L 체스판에서 나이트가 시작 위치에서 목표 위치까지 이동하는 최소 횟수를 구한다.

나이트는 (r, c)에서 (r±1, c±2) 또는 (r±2, c±1), 총 8가지 방향으로 이동한다. 체스판 밖으로는 나갈 수 없다.

입력

첫째 줄에 테스트 케이스 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 체스판 크기 L이 주어진다.

다음 줄에 나이트의 현재 위치 (r1, c1)이, 그 다음 줄에 목표 위치 (r2, c2)가 주어진다.

• 1 ≤ L ≤ 300
• 0 ≤ r1, c1, r2, c2 < L

출력

각 테스트 케이스마다 최소 이동 횟수를 출력한다.

예제 입력 1

3
8
0 0
7 0
100
0 0
99 99
3
0 0
2 2

예제 출력 1

5
66
4