나이트 이동: 골드 에디션

크기가 $N \times N$인 체스판이 있다. 행과 열은 1부터 $N$까지 번호가 매겨져 있다. 나이트가 $R_1$행 $C_1$열 칸에서 출발하여 $R_2$행 $C_2$열 칸으로 가려고 한다. 나이트를 출발 칸에서 도착 칸까지 최소 횟수로 이동시키는 데 필요한 이동 횟수를 구하라.

나이트는 한 축으로 2칸, 다른 축으로 1칸 이동한다. 나이트가 $(A, B)$에 있으면 $(A-2, B-1)$, $(A-2, B+1)$, $(A+2, B-1)$, $(A+2, B+1)$, $(A-1, B-2)$, $(A+1, B-2)$, $(A-1, B+2)$, $(A+1, B+2)$ 중 한 칸으로 이동할 수 있다. 나이트는 체스판 밖으로 나갈 수 없다.

$N$, $R_1$, $C_1$, $R_2$, $C_2$가 주어질 때, $(R_1, C_1)$에서 $(R_2, C_2)$까지 나이트가 이동하는 데 필요한 최소 횟수를 구하라.

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다섯 정수 $N$ ($3 \le N \le 20$), $R_1$, $C_1$, $R_2$, $C_2$ ($1 \le R_1, C_1, R_2, C_2 \le N$)가 한 줄에 주어진다.

각 테스트 케이스마다 "Case #i:"를 출력한다. 여기서 $i$는 1부터 시작하는 테스트 케이스 번호이다. 이어서 같은 줄에 $(R_1, C_1)$에서 $(R_2, C_2)$까지 필요한 최소 이동 횟수를 출력한다. 항상 이동이 가능하다고 가정한다. 각 테스트 케이스의 출력 뒤에는 빈 줄을 하나 남긴다.