406035: GYM102220 G Radar Scanner

There are $$$n$$$ rectangle radar scanners on the ground. The sides of them are all paralleled to the axes. The $$$i$$$-th scanner's bottom left corner is square $$$(a_i,b_i)$$$ and its top right corner is square $$$(c_i,d_i)$$$. Each scanner covers some squares on the ground.

You can move these scanners for many times. In each step, you can choose a scanner and move it one square to the left, right, upward or downward.

Today, the radar system is facing a critical low-power problem. You need to move these scanners such that there exists a square covered by all scanners.

Your task is to minimize the number of move operations to achieve the goal.

The first line of the input contains an integer $$$T(1\leq T\leq 1000)$$$, denoting the number of test cases.

In each test case, there is one integer $$$n(1\leq n\leq 100000)$$$ in the first line, denoting the number of radar scanners.

For the next $$$n$$$ lines, each line contains four integers $$$a_i,b_i,c_i,d_i(1\leq a_i,b_i,c_i,d_i\leq 10^9,a_i\leq c_i,b_i\leq d_i)$$$, denoting each radar scanner.

It is guaranteed that $$$\sum n\leq 10^6$$$.

For each test case, print a single line containing an integer, denoting the minimum number of steps.

1
2
2 2 3 3
4 4 5 5

2