1
2
1 3 3 3 
3 1 1 2 

9

output:7

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define p1(x) x.first
#define p2(x) x.second
int n;
const int MXN=1e6+30;
unsigned a[MXN],b[MXN],c[MXN],d[MXN],s[MXN];
unsigned* tmp;
inline unsigned  rkb(unsigned  x){
	return lower_bound(s+1,tmp,x)-s;
}
const int INF=4e9+1;
struct node{
	int mnw,mnx,mnc,mnd,mncx,mndx,tgc,tgd,mxc,mxd;
}T[MXN<<2];
pair<int,node>RV[200];

inline void upd(int x){
	T[x].mnw=min(T[lc(x)].mnw,T[rc(x)].mnw);
	T[x].mnx=min(T[lc(x)].mnx,T[rc(x)].mnx);
	T[x].mnc=min(T[lc(x)].mnc,T[rc(x)].mnc);
	T[x].mnd=min(T[lc(x)].mnd,T[rc(x)].mnd);
	T[x].mncx=min(T[lc(x)].mncx,T[rc(x)].mncx);
	T[x].mndx=min(T[lc(x)].mndx,T[rc(x)].mndx);
	T[x].mxc=max(T[lc(x)].mxc,T[rc(x)].mxc);
	T[x].mxd=max(T[lc(x)].mxd,T[rc(x)].mxd); 
}
inline void uc(int x,int c){
	if(T[x].tgc==c)return ;
	T[x].tgc=c;
	T[x].mnw=T[x].mndx+c;
	T[x].mncx=T[x].mnx+c;
	T[x].mnc=c;
	T[x].mxc=c;
}
inline void ud(int x,int d){
	if(T[x].tgd==d)return ;
	T[x].tgd=d;
	T[x].mnw=T[x].mncx+d;
	T[x].mndx=T[x].mnx+d;
	T[x].mnd=d;
	T[x].mxd=d;
}
inline void pd(int x){
	if(T[x].tgc){
		uc(lc(x),T[x].tgc);
		uc(rc(x),T[x].tgc);
		T[x].tgc=0;
	}
	if(T[x].tgd){
		ud(lc(x),T[x].tgd);
		ud(rc(x),T[x].tgd);
		T[x].tgd=0;
	}	
}
inline void bd(int x,int l,int r){
	T[x]={0,0,0,0,0,0,0,0,0,0};
	if(l==r){
		T[x]={s[l],s[l],0,0,s[l],s[l],0,0,0,0};
		return ;
	}
	int mid=l+r>>1;
	bd(lc(x),l,mid);
	bd(rc(x),mid+1,r);
	upd(x);
}
inline void chkmodc(int x,int l,int r,int L,int R,int c){
	if(L>R)return ;
//	cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<c<<" "<<T[x].mnc<<endl;
	if(c<=T[x].mnc)return ;
	if(L<=l&&r<=R&&c>=T[x].mxc){
		uc(x,c);
//		cout<<l<<"x"<<r<<"x"<<c<<"x"<<T[x].mnc<<"x"<<T[x].tgc<<endl;
		return ;
	}
	pd(x);
	 
	int mid=l+r>>1;
	if(L<=mid)chkmodc(lc(x),l,mid,L,R,c);
	if(R>mid)chkmodc(rc(x),mid+1,r,L,R,c);
	upd(x);
}
inline void chkmxc(int r,int c){chkmodc(1,1,n,1,r,c);}
inline void chkmodd(int x,int l,int r,int L,int R,int d){
	if(L>R)return ;
	if(d<=T[x].mnd)return ;
	if(L<=l&&r<=R&&d>=T[x].mxd){
		ud(x,d);
		return ;
	}
	pd(x);
	int mid=l+r>>1;
	if(L<=mid)chkmodd(lc(x),l,mid,L,R,d);
	if(R>mid)chkmodd(rc(x),mid+1,r,L,R,d);
	upd(x);
}
inline void chkmxd(int r,int d){chkmodd(1,1,n,1,r,d);}


bool vis[MXN<<2];
int ccc=0;
inline void ps(int x,node T){
	if(!vis[x])
	vis[x]=1,RV[++ccc]={x,T};
}
inline void ucrv(int x,int c){
	if(T[x].tgc==c)return ;
	ps(x,T[x]);
	T[x].tgc=c;
	T[x].mnw=T[x].mndx+c;
	T[x].mncx=T[x].mnx+c;
	T[x].mnc=c;
	T[x].mxc=c;
}
inline void udrv(int x,int d){
	if(T[x].tgd==d)return ;
	ps(x,T[x]);
	T[x].tgd=d;
	T[x].mnw=T[x].mncx+d;
	T[x].mndx=T[x].mnx+d;
	T[x].mnd=d;
	T[x].mxd=d;
}
inline void pdrv(int x){
	if(T[x].tgc){
		ucrv(lc(x),T[x].tgc);
		ucrv(rc(x),T[x].tgc);
		T[x].tgc=0;
	}
	
	if(T[x].tgd){
		udrv(lc(x),T[x].tgd);
		udrv(rc(x),T[x].tgd);
		T[x].tgd=0;
	}	
}
inline void chkmodcrv(int x,int l,int r,int L,int R,int c){
	if(L>R)return ;
//	cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<c<<" "<<T[x].mnc<<endl;
	if(c<=T[x].mnc)return ;
	if(L<=l&&r<=R&&c>=T[x].mxc){
		ucrv(x,c);
//	cout<<l<<"?"<<r<<"x"<<c<<"x"<<T[x].mnc<<"x"<<T[x].tgc<<endl;
		return ;
	}
	pdrv(x);
	 
	int mid=l+r>>1;
	if(L<=mid)chkmodcrv(lc(x),l,mid,L,R,c);
	if(R>mid)chkmodcrv(rc(x),mid+1,r,L,R,c);
	ps(x,T[x]);
	upd(x);
	
}
inline void chkmxcrv(int r,int c){chkmodcrv(1,1,n,1,r,c);}
inline void chkmoddrv(int x,int l,int r,int L,int R,int d){
	if(L>R)return ;
	if(d<=T[x].mnd)return ;
	if(L<=l&&r<=R&&d>=T[x].mxd){
		udrv(x,d);
//		cout<<l<<"x"<<r<<"x"<<d<<"x"<<T[x].mnw<<endl;
		return ;
	}
	
	pdrv(x);
	int mid=l+r>>1;
	if(L<=mid)chkmoddrv(lc(x),l,mid,L,R,d);
	if(R>mid)chkmoddrv(rc(x),mid+1,r,L,R,d);
	ps(x,T[x]);
	upd(x);
}
inline void chkmxdrv(int r,int d){chkmoddrv(1,1,n,1,r,d);}



inline int gt(int x,int l,int r,int L,int R){
	if(L>R)return 4e9+1;
	if(L<=l&&r<=R)return T[x].mnw;
	pdrv(x);
	int mid=l+r>>1;
	int res=4e9+1;
	if(L<=mid)res=min(res,gt(lc(x),l,mid,L,R));
	if(R>mid)res=min(res,gt(rc(x),mid+1,r,L,R));
	return res;
}
inline void clr(){
	while(ccc)vis[p1(RV[ccc])]=0,ccc--;
	RV[++ccc]={1,T[1]};
	vis[1]=1;
}
inline void rvk(){
	while(ccc){
		auto e=RV[ccc];
		T[p1(e)]=p2(e);
		vis[p1(e)] =0;
		ccc--;
	}
}
inline void chkmx(int x){
	int t=rkb(b[x]);
//	cout<<t<<" "<<c[x]<<" "<<d[x]<<endl;
	chkmxc(t-1,c[x]);
	chkmxd(t-1,d[x]);
//	clr();
}
unsigned sc[MXN],sd[MXN],sa[MXN],sb[MXN];
int p[MXN];
inline bool cmp(int x,int y){
	if(a[x]==a[y])return b[x]<b[y];
	return a[x]<a[y];
}
#define rd(x) scanf("%lld",&x)
signed main() {
//    freopen("inter.in","r",stdin);
//    freopen("inter.out","w",stdout);
	ios::sync_with_stdio(0);
	int t;
	rd(t);
	while(t--){
		rd(n);
		for(int i=1;i<=n;i++)rd(a[i]),rd(b[i]),rd(c[i]),rd(d[i]),
			s[i]=b[i],
			p[i]=i;
		if(n==1){
			printf("%lld\n",a[1]+b[1]+c[1]+d[1]);
			continue;
		}
		sort(s+1,s+n+1);
		tmp=unique(s+1,s+n+1);
		for(auto i=tmp;i!=s+n+10;i++)
			*i=4e9;
		sort(p+1,p+n+1,cmp);
		int res=1e18;
		bd(1,1,n);
		unsigned mn=1e9;
		sc[n+1]=sd[n+1]=sa[n+1]=sb[n+1]=0;
		for(int i=n;i>=1;i--)
			sc[i]=max(sc[i+1],c[p[i]]),
			sd[i]=max(sd[i+1],d[p[i]]),
			sa[i]=max(sa[i+1],a[p[i]]),
			sb[i]=max(sb[i+1],b[p[i]]);
		unsigned mx=0;
		for(int i=1;i<=n;i++){
			mn=min(mn,b[p[i]]);
			mx=max(mx,b[p[i]]);
			chkmx(p[i]);
			clr();
			chkmxcrv(n,sc[i+1]);
			chkmxdrv(n,sd[i+1]);
//			printf("%lld %lld %lld \n",rkb(mn),a[p[i]],gt(1,1,n,rkb(mn),n)); 
			if(T[1].mnw+a[p[i]]<res)
			res=min(res,a[p[i]]+gt(1,1,n,rkb(mn),i==n?rkb(mx)-1:n));
			rvk();
		}
		unsigned mxa=0,mxb=0; 
		for(int i=1;i<=n;i++){
			res=min(res,(int)max(mxa,sa[i+1])+max(mxb,sb[i+1])+c[p[i]]+d[p[i]]);

			mxa=max(mxa,a[p[i]]);
			mxb=max(mxb,b[p[i]]);
		}
		printf("%lld\n",res);
	}
	return 0; 
}