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 <= T <= 1000)$, denoting the number of test cases.
In each test case, there is one integer $n (1 <= n <= 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 <= a_i, b_i, c_i, d_i <= 10^9, a_i <= c_i, b_i <= d_i)$, denoting each radar scanner.
It is guaranteed that $sum n <= 10^6$.
For each test case, print a single line containing an integer, denoting the minimum number of steps.
## Input
The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there is one integer $n (1 <= n <= 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 <= a_i, b_i, c_i, d_i <= 10^9, a_i <= c_i, b_i <= d_i)$, denoting each radar scanner.It is guaranteed that $sum n <= 10^6$.
## Output
For each test case, print a single line containing an integer, denoting the minimum number of steps.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the number of cities, and $ k \in \mathbb{Z} $ the number of factories to place.
- Let $ G = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $, where each edge $ e \in E $ has weight $ w(e) \in \mathbb{Z}^+ $.
- Let $ L \subseteq V $ be the set of leaf nodes (degree-1 vertices), with $ |L| \geq k $.
**Constraints**
1. $ 1 \leq T \leq 10^3 $
2. $ 2 \leq n \leq 10^5 $, $ 1 \leq k \leq 100 $
3. $ 1 \leq w(e) \leq 10^5 $ for all $ e \in E $
4. $ |L| \geq k $
5. Sum of $ n $ across all test cases $ \leq 10^6 $
**Objective**
Select a subset $ S \subseteq L $ with $ |S| = k $ such that the sum of pairwise distances between all pairs of selected leaves is minimized:
$$
\min_{\substack{S \subseteq L \\ |S| = k}} \sum_{\substack{u, v \in S \\ u < v}} d(u, v)
$$
where $ d(u, v) $ is the shortest path distance (sum of edge weights) between nodes $ u $ and $ v $ in $ G $.