Knight Moves: Black Edition

You have a chessboard of size $N \times N$. The rows and columns are numbered from 1 to $N$. A knight starts on the cell at row $R_1$ and column $C_1$, and wants to reach the cell at row $R_2$ and column $C_2$. Move the knight from the starting cell to the destination in the minimum number of moves.

A knight's jump moves it 2 cells along one axis and 1 cell along the other. If the knight is at $(A, B)$, it may move to $(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)$, or $(A+1, B+2)$. The knight cannot leave the board.

Given $N$, $R_1$, $C_1$, $R_2$, and $C_2$, determine the minimum number of steps needed to move the knight from $(R_1, C_1)$ to $(R_2, C_2)$.

The first line contains a positive integer $T$, the number of test cases. Each case is a line with five integers $N$ ($3 \le N \le 10^{15}$), $R_1$, $C_1$, $R_2$, and $C_2$ ($1 \le R_1, C_1, R_2, C_2 \le N$).

For each test case, print "Case #i:" where $i$ is the test case number starting from 1, followed by the minimum number of steps. A solution is guaranteed to exist, so the knight can always reach the destination from the starting cell. Leave a blank line after the output of each test case. Follow the format shown in the sample output.