#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 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; }d[maxn]; bool operator<(node a,node b){ if(a.a!=b.a)return a.a<b.a; return a.b<b.b; } struct Int { int x; }; bool operator<(Int a,Int b){ if(d[a.x].b!=d[b.x].b)return d[a.x].b<d[b.x].b; return a.x<b.x; } 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 slv(){ bool FL=1; n=read();up(i,1,n)d[i].a=read(),d[i].b=read(),d[i].c=read(),d[i].d=read(),FL&=(d[i].b==0); 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()); if(FL){ up(i,1,n-1)res=min(res,(ll)d[i].a+(ll)mxc[i+1]+(ll)mxd[i+1]); printf("%lld\n",res); return; } vector<Int>vec; up(i,1,n){ vec.insert(lower_bound(vec.begin(),vec.end(),(Int){i}),(Int){i}); int mc=mxc[i+1],md=mxd[i+1]; down(j,int(vec.size())-1,0){ if(d[i].a+(ll)mc+(ll)md>=res)break; if(j!=n-1)res=min(res,(ll)d[i].a+(ll)d[vec[j].x].b+(ll)mc+(ll)md); mc=max(mc,d[vec[j].x].c),md=max(md,d[vec[j].x].d); } } 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; }