Problem: You are given n points on a plane. 

Please find the minimum sum of areas of two axis-aligned rectangles, such that each point is contained in at least one of these rectangles.

Note that the chosen rectangles can be degenerate. Rectangle contains all the points that lie inside it or on its boundary.

Input

The first line contains one integer t (1 ≤ t ≤ 2 ⋅ 10^5) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of points.

The following n lines contain the coordinates of the points x_i and y_i (0 ≤ x_i, y_i ≤ 10^9). It is guaranteed that the points are distinct.

It is guaranteed that the sum of values n over all test cases does not exceed 2⋅10^5.

Output

For each test case print one integer — the minimum sum of areas.

Example

Input


3
2
9 1
1 6
2
8 10
0 7
4
0 0
1 1
9 9
10 10


Output


0
0
2

Note

In the first two test cases the answer consists of 2 degenerate rectangles. In the third test case one of the possible answers consists of two rectangles 1 × 1 with bottom left corners (0,0) and (9,9).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 200005,INF = INT_MAX >> 1;
using ll = long long;
struct Point { int x,y; } a[N];
inline Point operator+ (const Point &a,const Point &b) {return {a.x + b.x,a.y + b.y};}
inline Point operator- (const Point &a,const Point &b) {return {a.x - b.x,a.y - b.y};}
inline ll cross(const Point &a,const Point &b) {return a.x * 1ll * b.y - a.y * 1ll * b.x;}
inline ll dot(const Point &a,const Point &b) {return a.x * 1ll * b.x + a.y * 1ll * b.y;}
struct Rect
{
    int l,r,d,u;
    Rect(int l = INF,int r = 0,int d = INF,int u = 0):l(l),r(r),d(d),u(u){ }
    inline void ins(const Point &a)
    { l = min(l,a.x);r = max(r,a.x);d = min(d,a.y);u = max(u,a.y); }
    inline ll s() {return ll(r - l) * (u - d);}
};
inline Rect operator+(const Rect &a,const Rect &b) {return {min(a.l,b.l),max(a.r,b.r),min(a.d,b.d),max(a.u,b.u)};}
int n;
ll ans;Rect aa;
namespace P1
{
    Rect ps[N],ss[N];
    void solve()
    {
        sort(a + 1,a + n + 1,[](Point a,Point b) {return a.x < b.x;});
        ps[0] = ss[n + 1] = Rect();
        for (int i = 1;i <= n;i++) ps[i] = ps[i - 1],ps[i].ins(a[i]);
        for (int i = n;i > 0;--i) ss[i] = ss[i + 1],ss[i].ins(a[i]);
        for (int i = 1;i < n;i++) ans = min(ans,ps[i].s() + ss[i + 1].s());
    }
    int main ()
    {
        solve();for (int i = 1;i <= n;i++) swap(a[i].x,a[i].y);
        swap(aa.l,aa.d);swap(aa.r,aa.u);solve();
        return 0;
    }
}
inline int lc(int pos) {return pos << 1;}
inline int rc(int pos) {return pos << 1 | 1;}
namespace P2
{
    Point b1[N],b2[N];int w1,w2;
    vector<Point> t[N << 2];int pp[N << 2];
    void build(int pos,int l,int r)
    {
        static Point st[N];int w = 0;
        for (int i = l;i <= r;i++)
        {
            Point t = {b2[i].x - aa.l,b2[i + 1].y - aa.d};
            while (w > 1 && cross(t - st[w - 1],st[w] - st[w - 1]) >= 0) --w;
            st[++w] = t;
        }
        t[pos] = vector<Point>(st + 1,st + w + 1);pp[pos] = w - 1;
        if (l == r) return;
        int mid = (l + r) >> 1;build(lc(pos),l,mid);build(rc(pos),mid + 1,r);
    }
    ll query(int pos,int l,int r,int ql,int qr,Point p)
    {
        if (l == ql && r == qr)
        {
            while(pp[pos] && dot(p,t[pos][pp[pos]]) >= dot(p,t[pos][pp[pos] - 1])) --pp[pos];
            return dot(p,t[pos][pp[pos]]);
        }
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(lc(pos),l,mid,ql,qr,p);
        if (ql > mid) return query(rc(pos),mid + 1,r,ql,qr,p);
        return min(query(lc(pos),l,mid,ql,mid,p),query(rc(pos),mid + 1,r,mid + 1,qr,p));
    }
    void solve()
    {
        sort(a + 1,a + n + 1,[](Point a,Point b) {return a.x < b.x;});
        w1 = w2 = 0;
        for (int i = 1;i <= n;i++)
            if (!w1 || (b1[w1].x < a[i].x && b1[w1].y > a[i].y)) b1[++w1] = a[i];
            else if (w1 && b1[w1].x == a[i].x) b1[w1].y = min(b1[w1].y,a[i].y);
        for (int i = n;i > 0;--i)
            if (!w2 || (b2[w2].x > a[i].x && b2[w2].y < a[i].y)) b2[++w2] = a[i];
            else if (w2 && b2[w2].x == a[i].x) b2[w2].y = max(b2[w2].y,a[i].y);
        if (w1 == 1 || w2 == 1) return;
        reverse(b2 + 1,b2 + w2 + 1);build(1,1,w2 - 1);
        int p1 = 1,p2 = 0;
        for (int i = 1;i < w1;i++)
        {
            while (p1 < w2 && b1[i + 1].x > b2[p1].x) ++p1;
            while (p2 + 1 < w2 && b1[i].y <= b2[p2 + 2].y) ++p2;
            if (p1 <= p2) ans = min(ans,query(1,1,w2 - 1,p1,p2,{aa.u - b1[i].y,aa.r - b1[i + 1].x}));
        }
    }
    int main ()
    {
        solve();
        for (int i = 1;i <= n;i++)
            a[i].x = INF - a[i].x;
        swap(aa.l = INF - aa.l,aa.r = INF - aa.r);
        solve();
        return 0;
    }
}
namespace P3
{
    Rect ps[N],ss[N];int m;
    inline bool chk(Rect a,Rect b) {return a.u >= b.u && b.d >= a.d;};
    struct SegTree
    {
        ll t[N << 2];
        SegTree() {
            // memset(t,63,sizeof(t));
            for (int i = 0;i < N * 4;i++) t[i] = 1ll << 61;
        }
        void init()
        {
            for (int i = m - 1;i > 0;--i) t[i] = min(t[lc(i)],t[rc(i)]);
        }
        ll query(int l,int r)
        {
            ll ret = LLONG_MAX >> 2;
            for (l += m - 1,r += m + 1;r - l > 1;l >>= 1,r >>= 1)
            {
                if (!(l & 1)) ret = min(ret,t[l ^ 1]);
                if (r & 1) ret = min(ret,t[r ^ 1]);
            }
            return ret;
        }
    } t1,t2,t3;
    int main ()
    {
        sort(a + 1,a + n + 1,[](Point a,Point b) {return a.x < b.x;});ps[0] = ss[n + 1] = Rect();
        for (int i = 1;i <= n;i++) ps[i] = ps[i - 1],ps[i].ins(a[i]);
        for (int i = n;i > 0;--i) ss[i] = ss[i + 1],ss[i].ins(a[i]);
        m = 1;while (m < n + 2) m <<= 1;
        for (int i = 1;i <= n;i++) t1.t[m + i] = a[i].x * ll(aa.u - aa.d) - ss[i + 1].d * ll(aa.r - aa.l);
        t1.init();
        for (int i = 1;i <= n;i++) t2.t[m + i] = a[i].x * ll(aa.u - aa.d) + ss[i + 1].u * ll(aa.r - aa.l);
        t2.init();
        for (int i = 1;i <= n;i++) t3.t[m + i] = a[i].x * ll(aa.u - aa.d) + (ss[i + 1].u - ss[i + 1].d) * ll(aa.r - aa.l);
        t3.init();
        for (int i = 1;i <= n;i++)
        {
            int l = i,r = n;
            while (l < r)
            {
                int x = (l + r) >> 1;
                if (chk(ps[i - 1],ss[x + 1])) r = x;else l = x + 1;
            }
            int p1 = l;l = i,r = p1;
            while (l < r)
            {
                int x = (l + r) >> 1;
                if (!chk(ss[x + 1],ps[i - 1])) r = x;else l = x + 1;
            }
            int p2 = l;
            ans = min(ans,ll(a[p1].x - a[i].x) * (aa.u - aa.d) + max(0ll,ll(ps[i - 1].u - ps[i - 1].d) * (aa.r - aa.l)));
            if (p2 < p1)
            {
                if (ss[p2 + 1].d < ps[i - 1].d)
                {
                    ans = min(ans,t1.query(p2,p1 - 1) - ll(aa.u - aa.d) * a[i].x + ll(aa.r - aa.l) * ps[i - 1].u);
                }
                else
                {
                    ans = min(ans,t2.query(p2,p1 - 1) - ll(aa.u - aa.d) * a[i].x - ll(aa.r - aa.l) * ps[i - 1].d);
                }
            }
            if (i < p2) ans = min(ans,t3.query(i,p2 - 1) - ll(aa.u - aa.d) * a[i].x);
        }
        return 0;
    }
}
int main ()
{
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--)
    {
        cin >> n;aa = Rect();
        for (int i = 1;i <= n;i++) cin >> a[i].x >> a[i].y,aa.ins(a[i]);
        ans = aa.s();if (!ans) {cout << ans << endl;continue;}
        P3::main();P2::main();P1::main();
        cout << ans << endl;
    }
    return 0;
}