Huge Knight

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

One knight move goes two cells along one axis and one cell along the other. A knight on $(A, B)$ can 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$, find the minimum number of moves that takes 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 test case is one line with five integers $N$, $R_1$, $C_1$, $R_2$, $C_2$. Here $3 \le N \le 10^{15}$, and $R_1$, $C_1$, $R_2$, $C_2$ are between 1 and $N$ inclusive.

For each test case, print the minimum number of moves that takes the knight from $(R_1, C_1)$ to $(R_2, C_2)$, one per line.

Assume a solution always exists, so every input gives a destination the knight can reach from its starting cell.