Huge Knight#6063
You have a chessboard of size N \times N. The rows and columns are numbered from to . In a cell located at row R_1 and column C_1, a knight is starting his journey. The knight wants to go to the cell located at row R_2 and column C_2. Move the knight from the starting cell to this destination cell with minimum number of moves.
As a reminder, a knight's jump moves him cells along one of the axes, and cell along the other one. In other words, if a knight is at , 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). Of course, the knight cannot leave the board.
Given , R_1, C_1, R_2 and C_2, determine the minimum number of steps necessary to move the knight from (R_1, C_1) to (R_2, C_2).
The first input line contains a positive integer, , indicating the number of test cases. Each case consists of a line containing five integers (3 \le N \le 10^{15}), R_1, C_1, R_2 and C_2 are between and inclusive.
For each test case, output the minimum number of steps needed to move the knight from (R_1, C_1) to (R_2, C_2). Assume that there will always be a solution, i.e., it's possible to move the knight from its starting cell to its destination cell.
Example 1