Background

Special for beginners, ^_^

Description

The input gives an $n×n$ chessboard, together with the coordinates of a starting position and a destination position. A knight makes its classic L-shaped moves in each of the eight directions. Find the minimum number of steps needed to travel from the starting coordinate to the destination coordinate.

Format

Input

The first input is an integer $n$, the number of test cases.

Each test case consists of three lines.

The first line is the size of the board $L(4≤L≤300)$;

The second and third lines give the knight's starting position and target position respectively $(0\dots L-1)$.

Output

Output the minimum number of moves the knight must make. If the starting position equals the target position, output $0$.

Samples

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0

Limitation

1s, 1024KiB for each test case.