#include<bits/stdc++.h> #define int long long #define doub long double using namespace std; const int maxn=1e6+7; int n; struct node{ int a,b,c,d; }p[maxn]; int ans=1e16; void dfs1(int i,int mxa,int mxb,int mxc,int mxd,int c1,int c2){ if(i==n+1){ if(c1!=0&&c2!=0)ans=min(ans,mxa+mxb+mxc+mxd); return; } dfs1(i+1,max(mxa,p[i].a),max(mxb,p[i].b),mxc,mxd,c1+1,c2); dfs1(i+1,mxa,mxb,max(mxc,p[i].c),max(mxd,p[i].d),c1,c2+1); dfs1(i+1,max(mxa,p[i].a),max(mxb,p[i].b),max(mxc,p[i].c),max(mxd,p[i].d),c1+1,c2+1); } void slv1(){ dfs1(1,0,0,0,0,0,0); cout<<ans<<endl; ans=1e16; return; } void slv5(){ for(int i=1;i<=n;i++)ans=min(ans,p[i].c+p[i].d); cout<<ans<<endl; ans=1e16; return; } void fk_std(){ int rnd=(n<=1000)?30000:200; for(int u=1;u<=rnd;u++){ random_shuffle(p+1,p+n+1); int mxa=0,mxb=0,mxc=0,mxd=0; int c1=0,c2=0; for(int i=1;i<=n;i++){ int dta=max(mxa,p[i].a)-mxa; int dtb=max(mxb,p[i].b)-mxb; int dtc=max(mxc,p[i].c)-mxc; int dtd=max(mxd,p[i].d)-mxd; if(dta+dtb<dtc+dtd){ c1++; mxa=max(mxa,p[i].a); mxb=max(mxb,p[i].b); } else if(dta+dtb>dtc+dtd){ c2++; mxc=max(mxc,p[i].c); mxd=max(mxd,p[i].d); } } if(c1>0&&c2>0)ans=min(ans,mxa+mxb+mxc+mxd); } cout<<ans<<endl; ans=1e16; } inline void slv(){ cin>>n; for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b>>p[i].c>>p[i].d; if(n<=10){ slv1(); return; } bool b=true; for(int i=1;i<=n;i++){ if(p[i].a!=0||p[i].b!=0){b=false;break;} } if(b){ slv5(); return; } fk_std(); } inline void MT(){ int t; cin>>t; while(t--)slv(); } signed main(){ srand(time(0)); // freopen("b.in","r",stdin); // freopen("inter.out","w",stdout); MT(); }