#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]; 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; } ll sol3(){ int res=0; sort(d+1,d+n+1,cmp); ll g=1e10; 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); up(i,1,n-1)res=max(res,d[i].a),g=min(g,res+(ll)d[i].b+(ll)mxc[i+1]+(ll)mxd[i+1]); return g; } void Unique(){ vector<int>A; up(i,1,n)A.p_b(d[i].b); sort(A.begin(),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 stack<pair<int,node> >S; void pu(int p){ S.push(m_p(p,d[p])); RES(p)=mg(RES(ls(p)),RES(rs(p))); } void cl(int p,ll l1,ll l2){ S.push(m_p(p,d[p])); 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; S.push(m_p(p,d[p])); 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)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); } void upd(int l,int s,int t,int p,nd V){ if(s==t){ V=nd(V.P,RES(p).C,RES(p).D); RES(p)=V;return; }pd(p);int mid=s+t>>1; if(l<=mid)upd(l,s,mid,ls(p),V);else upd(l,mid+1,t,rs(p),V);pu(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(!S.empty())S.pop(); } void DEL2(){ while(!S.empty()){ auto it=S.top();S.pop(); d[it.p1]=it.p2; } } int gbc(int s,int t,int p,ll C){ if(RES(p).C>=C)return 0; if(s==t)return s;pd(p); int mid=s+t>>1; if(RES(rs(p)).C>=C)return gbc(s,mid,ls(p),C); return gbc(mid+1,t,rs(p),C); } int gbd(int s,int t,int p,ll D){ if(RES(p).D>=D)return 0; if(s==t)return s;pd(p); int mid=s+t>>1; if(RES(rs(p)).D>=D)return gbd(s,mid,ls(p),D); return gbd(mid+1,t,rs(p),D); } void ubc(int x,int w){ if(!x)return; int pos=gbc(1,n,1,w); if(pos)gmx(1,min(pos,x),1,n,1,w,-1); } void ubd(int x,int w){ if(!x)return; int pos=gbd(1,n,1,w); if(pos)gmx(1,min(pos,x),1,n,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(); 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; T.bd(1,n,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){ T.upd(d[i].rkb,1,n,1,nd(d[i].b,0,0)); T.ubc(d[i].rkb-1,d[i].c); T.ubd(d[i].rkb-1,d[i].d); T.DEL1(); if(i+1<=n)T.ubc(n,mxc[i+1]); if(i+1<=n)T.ubd(n,mxd[i+1]); if(i!=n)res=min(res,T.qry(1,n,1,n,1).PCD+d[i].a); else res=min(res,T.qry(1,MX-1,1,n,1).PCD+d[i].a); //cerr<<"test "<<i<<' '<<T.qry(1,n,1,n,1).PCD+d[i].a<<endl; T.DEL2(); }res=min(res,sol3()); 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; }