Sliding Puzzle

All submissions for this problem are available.

Famous company Strange Puzzles Inc. has designed a brand new series of puzzles aimed at students who are fond of competitive programming. In this problem we are going to consider one of them named "Sliding Windows".

The puzzle consists of an infinite two-dimensional plane and n rectangles located in it. Each of the rectangles has its sides parallel to the coordinate axes. The puzzle is considered to be solved if for any two rectangles it is true that at least one of them is covered by the other one. Formally, rectangle i covers rectangle j if and only if for any point of the plane (x, y) which lies inside rectangle j, it also lies inside rectangle i.

The only action that you are allowed to perform is to shift the rectangles up, down, left or right. In one unit of time you can take one of the rectangles and shift it exactly by 1 unit in one of these four directions.

As a true competitive programmer you wonder what the minimum number of time units required to solve the puzzle is (if it can be solved at all).

Input

• The first line of the input contains a single integer T — the number of test cases in the given input. Then follow T descriptions of individual tests.
• The first line of teach testcase contains a single integer, n — the number of rectangles.
• The i^th of the next n lines contains four integers l_i, b_i, r_i and u_i — this signifies that (l_i, b_i) is the lower left corner and (r_i, u_i) is the upper right corner of the i^th rectangle.

Output

• If the puzzle can not be solved for the given set of rectangles print  -1 in the only line of the output. Otherwise print a single integer equal to the minimum number of time units required to solve the puzzle.

Constraints

• 1 ≤ T ≤ 200000
• 1 ≤ n ≤ 200000
•  - 10⁹ ≤ l_i < r_i ≤ 10⁹
•  - 10⁹ ≤ b_i < u_i ≤ 10⁹
• It's guaranteed that the sum of n over all test cases in one test file won't exceed 1000000.

Example

Input:
2
2
0 -1 1 2
-1 0 2 1
3
0 0 4 1
-1 1 1 2
2 1 5 2

Output:
-1
4

Explanation

Testase 1: No matter how we move the rectangles, one rectangle cannot cover the other rectangle. Hence the answer is -1.

Testcase 2: One of the optimal solutions is to shift the first rectangle up by 1 unit, second rectangle right by 1 unit and third rectangle left by 2 units. This takes a total of 4 time units and hence that is the answer.