Knight's Move

A knight is placed on a chessboard. In a single move the knight jumps in an L-shape: two squares in one direction and then one square perpendicular to it. From any square it can therefore reach up to 8 different squares.

Given the target square the knight wants to reach, determine the minimum number of moves needed to get there.

The first line contains the number of test cases.

Each test case consists of three lines.

• Line 1: the side length $l$ of the chessboard ($4 \le l \le 300$). The board is $l \times l$, and each square is written as a coordinate pair in $\{0, \dots, l-1\} \times \{0, \dots, l-1\}$.
• Line 2: the coordinates of the square the knight currently stands on.
• Line 3: the coordinates of the target square the knight wants to reach.

For each test case, print on its own line the minimum number of moves the knight needs to travel from the starting square to the target square.