. 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.

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 ai,bi,ci,di(1≤ai,bi,ci,di≤109,ai≤ci,bi≤di)

, denoting each radar scanner.

It is guaranteed that ∑n≤106

.

Output

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

Example

1

2

2 2 3 3

4 4 5 5

2

题解：由于横纵方向地位相同，我们不妨来看横方向，题目要找一点x使得n条线段经过平移最少次数，至少重合一点。
假设那一点就为x，那么一条线段至少与x有交点的话，所需距离为：d=（|l-x|+|r-x|-|r-l|)/2,纸上画一遍即可。我们要找的是所有线段移动的距离之和最小，那么只需Σd最小，
由于d中的|r-l|为常数，所以我们只需要求Σ（|l-x|+|r-x|)最小，那么x就是所有l，r的中位数了～～。题目难得就是转化～～

#include<iostream>

#include<cstring>

#include<string>

#include<queue>

#include<stack>

#include<algorithm>

#include<stdio.h>

#include<map>

#include<set>

using namespace std;

typedef long long ll;

const int maxn=;

struct node

{

    ll l,r;

}q[maxn],w[maxn];

ll n,a[maxn*];

ll ok(node q[])

{

    int top=;

    for(int i=;i<=n;i++){

        a[++top]=q[i].l;

        a[++top]=q[i].r;

    }

    sort(a+,a++top);

    ll x=(a[top/]+a[top/+])/;

    ll ans=;

    for(int i=;i<=n;i++){

        ans+=(abs(q[i].l-x)+abs(q[i].r-x)-(q[i].r-q[i].l))/;

    }

    return ans;

}

int main()

{

    ios::sync_with_stdio();

    int T;

    cin>>T;

    while(T--){

        cin>>n;

        for(int i=;i<=n;i++){

            cin>>q[i].l>>w[i].l>>q[i].r>>w[i].r;

        }

        ll ans=;

        ans+=ok(q);

        ans+=ok(w);

        cout<<ans<<endl;

    }

    return ;

}