NITT7 - Grid Travel

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

Added by:jack(chakradarraju)
Date:2012-09-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2012-10-02 15:24:41 Francky
This problem isn't for tutorial, it should be hidden. What a joke.
Here is for classical, please take this in consideration.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.