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>
typedef long long LL;
#define pb push_back
#define pii std::pair<LL,LL>
#define opt operator
const LL maxn=2e5+9,inf=1e18;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
void Chkmax(LL &x,LL y){
	if(y>x) x=y;
}
struct point{
	LL x,y;
};
bool cmpx(const point A,const point B){
	return A.x<B.x;
}
void pre_suf(point *A,pii *prex,pii *prey,pii *sufx,pii *sufy,LL n){
	prex[0]=prey[0]=pii(inf,-inf);
    for(LL i=1;i<=n;++i){
		LL x(A[i].x),y(A[i].y);
		prex[i]=prex[i-1]; prey[i]=prey[i-1];
		Chkmin(prex[i].first,x); Chkmax(prex[i].second,x);
		Chkmin(prey[i].first,y); Chkmax(prey[i].second,y);
	}
	sufx[n+1]=sufy[n+1]=pii(inf,-inf);
	for(LL i=n;i>=1;--i){
		LL x(A[i].x),y(A[i].y);
		sufx[i]=sufx[i+1]; sufy[i]=sufy[i+1];
		Chkmin(sufx[i].first,x); Chkmax(sufx[i].second,x);
		Chkmin(sufy[i].first,y); Chkmax(sufy[i].second,y);
	}
}
LL Calc(pii A,pii B){
	return (A.second-A.first)*(B.second-B.first);
}
namespace sub1{
	LL Solve(point *A,LL n){
		static pii prex[maxn],prey[maxn],sufx[maxn],sufy[maxn];
		LL ret(inf);
		for(LL ti=1;ti<=2;++ti){
			std::sort(A+1,A+1+n,cmpx);
			pre_suf(A,prex,prey,sufx,sufy,n);
			Chkmin(ret,Calc(prex[n],prey[n]));
			for(LL i=1;i<n;++i){
				Chkmin(ret,Calc(prex[i],prey[i])+Calc(sufx[i+1],sufy[i+1]));
			}
			for(LL i=1;i<=n;++i) std::swap(A[i].x,A[i].y);
		}
		return ret;
	}
}
namespace sub2{
	LL H,W;
	LL a[maxn];
	LL mi[maxn<<2];
	void Build(LL nw,LL l,LL r){
		if(l==r){
			mi[nw]=a[l];
			return;
		}
		LL mid(l+r>>1);
		Build(nw<<1,l,mid); Build(nw<<1|1,mid+1,r);
		mi[nw]=std::min(mi[nw<<1],mi[nw<<1|1]);
	}
    LL Query(LL nw,LL l,LL r,LL lt,LL rt){
		if(lt<=l && rt>=r) return mi[nw];
		LL mid(l+r>>1),ret(inf);
		if(lt<=mid) Chkmin(ret,Query(nw<<1,l,mid,lt,rt));
		if(rt>mid) Chkmin(ret,Query(nw<<1|1,mid+1,r,lt,rt));
		return ret;
	}
	LL Get1(point *A,pii *prey,pii *sufy,LL n,LL op){
		LL ret(inf);
        for(LL i=1;i<=n;++i){
			if(op==1){
				a[i]=-A[i].x*H-prey[i-1].first*W;
			}else{
				a[i]=A[i].x*H-prey[i-1].first*W;
			}
		}
		Build(1,1,n);
		for(LL i=1;i<n;++i){
			LL upy(sufy[i+1].second),lowy(sufy[i+1].first);
			LL l(1),r(i),rt(0);
			while(l<=r){
				LL mid(l+r>>1);
				if(prey[mid-1].second<=upy){
					rt=mid; l=mid+1;
				}else r=mid-1;
			}
			l=1,r=i; LL lt(0);
			while(l<=r){
				LL mid(l+r>>1);
				if(prey[mid-1].first<=lowy){
					lt=mid; r=mid-1;
				}else l=mid+1;
			}
			if(!lt) continue;
			Chkmax(lt,2);
			if(lt>rt) continue;
			if(op==1){
				Chkmin(ret,A[i].x*H+upy*W+Query(1,1,n,lt,rt));
			}else{
				Chkmin(ret,-A[i].x*H+upy*W+Query(1,1,n,lt,rt));
			}
		}
		return ret;
	}
	LL Get2(point *A,pii *prey,pii *sufy,LL n,LL op){
		LL ret(inf);
		for(LL i=1;i<n;++i){
			LL upy(sufy[i+1].second),lowy(sufy[i+1].first);
			LL l(1),r(i),nw(0);
			while(l<=r){
				LL mid(l+r>>1);
				if(prey[mid-1].first>=lowy && prey[mid-1].second<=upy){
					nw=mid; l=mid+1;
				}else r=mid-1;
			}
			l=nw;
			if(op==1){
				Chkmin(ret,(A[i].x-A[l].x)*H+(upy-lowy)*W);
			}else{
				Chkmin(ret,(A[l].x-A[i].x)*H+(upy-lowy)*W);
			}
		}
		return ret;
	}
	LL Solve(point *A,LL n){
		LL ret(inf);
		static pii prex[maxn],prey[maxn],sufx[maxn],sufy[maxn];
		std::sort(A+1,A+1+n,cmpx);
		pre_suf(A,prex,prey,sufx,sufy,n);
		H=prey[n].second-prey[n].first; W=prex[n].second-prex[n].first;
		for(LL ti=1;ti<=2;++ti){
			Chkmin(ret,Get1(A,prey,sufy,n,ti));
			Chkmin(ret,Get2(A,prey,sufy,n,ti));
			for(LL i=1;i<=n;++i){
				std::swap(prey[i],sufy[n-i+1]);
			}
			for(LL i=1;i<=n/2;++i){
				std::swap(A[i],A[n-i+1]);
			}
		}
		return ret;
	}
}
namespace sub3{
	struct node{
		LL k,b;
	};
	node p[maxn];
	std::vector<node> V[maxn<<2];
	bool cmp1(const point A,const point B){
		return A.x<B.x;
	}
	bool cmp2(const point A,const point B){
		return A.y<B.y;
	}
	LL Calc(node A,pii B){
		return A.k*B.first+A.b*B.second;
	}
	bool Check(node A1,node A2,node A3){
		pii tmp1(pii(A2.b-A1.b,A1.k-A2.k)),
		    tmp2(pii(A3.b-A2.b,A2.k-A3.k));
        LL x(tmp1.first*tmp2.second),y(tmp2.first*tmp1.second);
		return x<=y;
	}
	void Add(std::vector<node> &A,node B){
		if(A.size()){
			if(A.back().k==B.k){
				if(A.back().b<B.b) return;
				else{
					A.pop_back(); A.pb(B); return;
				}
			}
		}
		while(A.size()>2){
			LL sz(A.size());
			if(Check(B,A[sz-1],A[sz-2])) A.pop_back();
			else break;
		}
		A.pb(B);
	}
	void Build(LL nw,LL l,LL r){
	    std::vector<node>().swap(V[nw]);
		if(l==r){
			V[nw].pb(p[l]); return;
		}
		LL mid(l+r>>1);
		Build(nw<<1,l,mid); Build(nw<<1|1,mid+1,r);
		LL lt(0),rt(0),sz1(1ll*V[nw<<1].size()),sz2(1ll*V[nw<<1|1].size());
		while(lt<sz1 && rt<sz2){
			if(V[nw<<1][lt].k>V[nw<<1|1][rt].k){
				Add(V[nw],V[nw<<1][lt]); ++lt;
			}else{
				Add(V[nw],V[nw<<1|1][rt]); ++rt;
			}
		}
		while(lt<sz1) Add(V[nw],V[nw<<1][lt]),++lt;
		while(rt<sz2) Add(V[nw],V[nw<<1|1][rt]),++rt;
	}
	LL Query(LL nw,LL ll,LL rr,LL lt,LL rt,pii v){
		if(lt<=ll && rt>=rr){
			LL l(0),r(1ll*V[nw].size()-2); LL ret(Calc(V[nw].back(),v));
			while(l<=r){
				LL mid(l+r>>1);
				LL val1(Calc(V[nw][mid],v)),val2(Calc(V[nw][mid+1],v));
				if(val1<=val2){
					Chkmin(ret,val1); l=mid+1;
				}else{
					Chkmin(ret,val2);
					r=mid-1;
				}
			}
			return ret;
		}
		LL mid(ll+rr>>1),ret(inf);
		if(lt<=mid) Chkmin(ret,Query(nw<<1,ll,mid,lt,rt,v));
		if(rt>mid) Chkmin(ret,Query(nw<<1|1,mid+1,rr,lt,rt,v));
		return ret;
	}
	LL Get(point *A,LL n){
		static point a[maxn],b[maxn];
		static LL asufy[maxn],bsufx[maxn];
		for(LL i=1;i<=n;++i){
			a[i]=b[i]=A[i];
		}
		std::sort(a+1,a+1+n,cmp1);
		std::sort(b+1,b+1+n,cmp2);
		LL lowx(a[1].x),upx(a[n].x),lowy(b[1].y),upy(b[n].y);
		{
			asufy[n+1]=upy;
			for(LL i=n;i>=1;--i) asufy[i]=std::min(asufy[i+1],a[i].y);
		}
		{
			bsufx[n+1]=upx;
			for(LL i=n;i>=1;--i) bsufx[i]=std::min(bsufx[i+1],b[i].x);
			for(LL i=1;i<=n;++i){
				p[i]=(node){b[i].y-lowy,upx-bsufx[i+1]};
			}
			Build(1,1,n);
		}
		LL ret(inf);
		LL lt(n),rt(n);
		for(LL i=n;i>=1;--i){
			while(lt>1 && b[lt-1].y>=asufy[i+1]) --lt;
//			while(rt && bsufx[rt]>a[i].x) --rt;
//			while(rt && bsufx[rt]>=a[i].x) --rt;
			while(rt && bsufx[rt+1]>=a[i].x) --rt;
			if(lt<=rt){
				pii nw;
				nw.first=a[i].x-lowx;
				nw.second=upy-asufy[i+1];
//				LL tmp(Query(1,1,n,lt,rt-1,nw));
				LL tmp(Query(1,1,n,lt,rt,nw));
				Chkmin(ret,tmp);
			}
		}
		return ret;
	}
	LL Solve(point *A,LL n){
		LL ret1(0); ret1=Get(A,n);
		for(LL i=1;i<=n;++i) A[i].x*=-1;
		LL ret2(Get(A,n));
		return std::min(ret1,ret2);
	}
}
LL n;
point a[maxn];
int main(){
//	freopen("y1.txt","r",stdin);
	LL T=Read();
	while(T--){
		n=Read();
		for(LL i=1;i<=n;++i){
			LL x(Read()),y(Read());
            a[i]=(point){x,y};
		}
		LL ret1(sub1::Solve(a,n));
		LL ret2(sub2::Solve(a,n));
		LL ret3(sub3::Solve(a,n));
		LL ret(std::min(ret1,std::min(ret2,ret3)));
		printf("%lld\n",ret);
	}
	return 0;
}