The real Manhattan distance

Given two points (x, y, floor), compute the walking distance: down from each floor, plus Manhattan street distance.

Easy2MathImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

Manhattan is laid out as a grid of streets, and very tall buildings stand all over the island.

Suppose you walk from your apartment at x=3x=3, y=4y=4, floor 3 to a friend's apartment at x=3x=3, y=5y=5, floor 2. The distance between the two points is the distance from your apartment down to the street, plus the distance along the streets to your friend's building, plus the distance from the street up to your friend's apartment.

The distance between two consecutive floors is 1. In Manhattan the street distance between two points is the absolute difference of the xx coordinates plus the absolute difference of the yy coordinates. Floor 0 means the point is already at street level.

For example, the distance from (3,4,3)(3, 4, 3) to (3,5,2)(3, 5, 2) is 3 for going down the first building, 0 for moving along xx, 1 for moving along yy, and 2 for going up the second building, so 3+0+1+2=63 + 0 + 1 + 2 = 6. More of that walk happens inside the buildings than on the streets.

When the start and the destination are the same point, you still ride down to the street and back up, so the distance is the sum of the two floor numbers.

Given two points, compute the distance in meters you have to walk.

Input

The first line contains the number of test cases TT.

Each of the next TT lines contains six integers x1x_1, y1y_1, f1f_1, x2x_2, y2y_2, f2f_2 separated by spaces, describing two points. f1f_1 is the floor of the first point and f2f_2 is the floor of the second point.

1T1001 \le T \le 100, 0x1,y1,f1,x2,y2,f2100000 \le x_1, y_1, f_1, x_2, y_2, f_2 \le 10000

Output

For each test case, print the distance between the two points on its own line.