A square of side length a is in the first quadrant sharing the x and y axis. Given two points P1(x1, y1) and P2(x2, y2) on the boundary of the square, find the minimum distance between those two points by travelling only on the boundary of the square.

Input

First line containing T (<= 50) denoting the number of test case.

Then T lines is of the format a x1 y1 x2 y2.

3 <= a <= 10000

Both P1 and P2 will lie on the boundary of the square.

Output

For each test case print the minimum distance to reach P2 from P1 by travelling on the boundary of the square.

Example

Input:
2
4469
2770 0 4469 1117
2562
2083 0 0 652

Output:
2816
2735