#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define m_p make_pair #define p_b push_back #define p1 first #define p2 second using namespace std; typedef long long ll; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n; int mxc[maxn],mxd[maxn]; vector<int>A; struct node { int a,b,c,d,rkb; }d[maxn]; bool operator<(node a,node b){ if(a.a!=b.a)return a.a<b.a; return a.b<b.b; } bool cmp(node a,node b){ return a.b<b.b; } ll sol1(){ ll ma=0,mb=0; up(i,1,n)ma=max(ma,(ll)d[i].a),mb=max(mb,(ll)d[i].b); ll ms=1e18; up(i,1,n)ms=min(ms,(ll)d[i].c+(ll)d[i].d); return ma+mb+ms; } ll sol2(){ ll mc=0,md=0; up(i,1,n)mc=max(mc,(ll)d[i].c),md=max(md,(ll)d[i].d); ll ms=1e18; up(i,1,n)ms=min(ms,(ll)d[i].a+(ll)d[i].b); return mc+md+ms; } void Unique(){ A.clear(); up(i,1,n)A.p_b(d[i].b); sort(A.begin(),A.end()); A.erase(unique(A.begin(),A.end()),A.end()); up(i,1,n)d[i].rkb=lower_bound(A.begin(),A.end(),d[i].b)-A.begin()+1; } struct nd { int P,C,D,PC,PD;ll PCD; nd(ll _P,ll _C,ll _D,ll _PC,ll _PD,ll _PCD){ P=_P,C=_C,D=_D,PC=_PC,PD=_PD,PCD=_PCD; } nd(ll _P,ll _C,ll _D){ P=_P,C=_C,D=_D; PC=_P+_C,PD=_P+_D,PCD=_P+_C+_D; } nd(){ P=C=D=INT_MAX/2,PC=PD=P*2,PCD=P*3ll; } //min pos c d pos+c pos+d pos+c+d }; nd mg(nd a,nd b){ return nd(min(a.P,b.P),min(a.C,b.C),min(a.D,b.D),min(a.PC,b.PC),min(a.PD,b.PD),min(a.PCD,b.PCD)); } void deal(nd &a,ll tagC,ll tagD){ if(tagC==-1&&tagD==-1)return; if(tagC!=-1&&tagD!=-1){ a.C=tagC,a.D=tagD; a.PC=a.P+tagC,a.PD=a.P+tagD,a.PCD=a.P+tagC+tagD; return; } if(tagC!=-1){ a.C=tagC; a.PC=a.P+tagC,a.PCD=a.PD+tagC; return; }else { a.D=tagD; a.PD=a.P+tagD,a.PCD=a.PC+tagD; return; } } struct SegTree { struct node { nd RES; int lz1,lz2; node(){ lz1=lz2=-1; } }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define RES(p) d[p].RES #define lz1(p) d[p].lz1 #define lz2(p) d[p].lz2 pair<int,node>S[2005]; int tp; bool vis[maxn<<2]; void pu(int p){ if(!vis[p])S[++tp]=m_p(p,d[p]),vis[p]=1; RES(p)=mg(RES(ls(p)),RES(rs(p))); } void cl(int p,ll l1,ll l2){ if(!vis[p])S[++tp]=m_p(p,d[p]),vis[p]=1; deal(RES(p),l1,l2); if(l1!=-1)lz1(p)=l1; if(l2!=-1)lz2(p)=l2; }void pd(int p){ if(lz1(p)==-1&&lz2(p)==-1)return; if(!vis[p])S[++tp]=m_p(p,d[p]),vis[p]=1; cl(ls(p),lz1(p),lz2(p)),cl(rs(p),lz1(p),lz2(p)); lz1(p)=lz2(p)=-1; }void bd(int l,int r,int p){ lz1(p)=lz2(p)=-1,RES(p)=nd(); if(l==r){ RES(p)=nd(A[l-1],0,0); return; } int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));RES(p)=mg(RES(ls(p)),RES(rs(p))); } void gmx(int l,int r,int s,int t,int p,int tgC,int tgD){ if(l<=s&&t<=r){ cl(p,tgC,tgD);return; }pd(p);int mid=s+t>>1; if(l<=mid)gmx(l,r,s,mid,ls(p),tgC,tgD); if(r>=mid+1)gmx(l,r,mid+1,t,rs(p),tgC,tgD);pu(p); } void DEL1(){ while(tp)vis[S[tp--].p1]=0; } void DEL2(){ while(tp){ vis[S[tp].p1]=0; d[S[tp].p1]=S[tp].p2; tp--; } } int gbc(int s,int t,int p,ll C,int X){ if(s>X)return X+1; if(s==t){ if(RES(p).C>=C)return 0; return s; }pd(p); int mid=s+t>>1; if(RES(ls(p)).C<C)return gbc(s,mid,ls(p),C,X); return gbc(mid+1,t,rs(p),C,X); } int gbd(int s,int t,int p,ll D,int X){ if(s>X)return X+1; if(s==t){ if(RES(p).D>=D)return 0; return s; }pd(p); int mid=s+t>>1; if(RES(ls(p)).D<D)return gbd(s,mid,ls(p),D,X); return gbd(mid+1,t,rs(p),D,X); } void ubc(int x,int w){ if(!x)return; int pos=gbc(1,A.size(),1,w,x); if(pos<=x)gmx(pos,x,1,A.size(),1,w,-1); } void ubd(int x,int w){ if(!x)return; int pos=gbd(1,A.size(),1,w,x); if(pos<=x)gmx(pos,x,1,A.size(),1,-1,w); } nd qry(int l,int r,int s,int t,int p){ if(l>r)return nd(); if(l<=s&&t<=r)return RES(p);pd(p); int mid=s+t>>1;nd RES; if(l<=mid)RES=mg(RES,qry(l,r,s,mid,ls(p)));if(r>=mid+1)RES=mg(RES,qry(l,r,mid+1,t,rs(p))); return RES; } }T; void slv(){ n=read();up(i,1,n)d[i].a=read(),d[i].b=read(),d[i].c=read(),d[i].d=read(); if(n==1){ ll res=d[1].a+d[1].b;res+=d[1].c+d[1].d; printf("%lld\n",res);return; } Unique();sort(d+1,d+n+1); mxc[n+1]=mxd[n+1]=0; down(i,n,1)mxc[i]=max(mxc[i+1],d[i].c),mxd[i]=max(mxd[i+1],d[i].d); ll res=min(sol1(),sol2()); //cerr<<"test "<<res<<endl; int SZ=A.size(); T.bd(1,SZ,1); int MX=0,MX2=0; up(i,1,n)MX=max(MX,d[i].rkb),MX2=max(MX2,d[i].b); up(i,1,n){ //cerr<<"rkb:"<<d[i].rkb<<' '<<d[i].c<<' '<<d[i].d<<endl; T.ubc(d[i].rkb-1,d[i].c); T.ubd(d[i].rkb-1,d[i].d); T.DEL1(); //cerr<<"TEST "<<mxc[i+1]<<' '<<mxd[i+1]<<endl; if(i+1<=n)T.ubc(SZ,mxc[i+1]),T.ubd(SZ,mxd[i+1]); //cerr<<"PCD : "<<T.qry(1,1,1,SZ,1).PCD<<' '<<T.qry(2,2,1,SZ,1).PCD<<endl; if(i<n){ if(T.RES(1).PCD+d[i].a<res)res=min(res,T.qry(d[i].rkb,SZ,1,SZ,1).PCD+d[i].a); } else { if(T.RES(1).PCD+d[i].a<res)res=min(res,T.qry(d[i].rkb,SZ-1,1,SZ,1).PCD+d[i].a); } //cerr<<"now = "<<T.qry(1,SZ,1,SZ,1).PCD<<' '<<res<<endl; T.DEL2(); }printf("%lld\n",res); }int main(){ // freopen("inter.in","r",stdin); // freopen("inter.out","w",stdout); int t=read();while(t--)slv(); fclose(stdin); fclose(stdout); return 0; }