// 40pts #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 9; struct node { int a, b, c, d; } s[N]; int _, n; namespace sub1 { // ai = bi = 0; bool chk() { for (int i = 1; i <= n; i++) { if (s[i].a || s[i].b) return 0; } return 1; } void Main() { int ans = 0x7FFFFFFF; for (int i = 1; i <= n; i++) { ans = min(ans, s[i].c + s[i].d); } printf("%d\n", ans); } } namespace sub2 { ll ans = 1e18; void dfs(int u, int mxa, int mxb, int mxc, int mxd, int flx, int fly) { if ((ll)mxa + mxb + mxc + mxd >= ans) return; if (u > n) { if (flx && fly) ans = min(ans, (ll)mxa + mxb + mxc + mxd); return; } dfs(u + 1, max(mxa, s[u].a), max(mxb, s[u].b), mxc, mxd, 1, fly); dfs(u + 1, mxa, mxb, max(mxc, s[u].c), max(mxd, s[u].d), flx, 1); } void Main() { ans = 1e18, dfs(1, 0, 0, 0, 0, 0, 0); printf("%lld\n", ans); } } namespace sub3 { void Main() { int mnx = 2e9, mny = 2e9; for (int i = 1; i <= n; i++) { mnx = min(mnx, s[i].a + s[i].b); mny = min(mny, s[i].c + s[i].d); } ll ans = 1e18; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int mxc = 0, mxd = 0, flx = 0, fly = 0; int mxa = s[i].a, mxb = s[j].b; for (int k = 1; k <= n; k++) { if (s[k].a > s[i].a || s[k].b > s[j].b) mxc = max(mxc, s[k].c), mxd = max(mxd, s[k].d), fly = 1; else mxa = max(mxa, s[k].a), mxb = max(mxb, s[k].b), flx = 1; } ans = min(ans, (ll)(flx ? mxa + mxb : mnx) + (fly ? mxc + mxd : mny)); } } printf("%lld\n", ans); } } // namespace sub4 { // void Main() { // for (int i = 1; i <= n; i++) { // int mxb = 0, mxc = 0, mxd = 0; // for (int j = 1; j <= n; j++) { // if (s[j].a > s[i].a) mxc = max(mxc, s[j].c), mxd = max(mxd, s[j].d); // } // for (int j = 1; j <= n; j++) { // if (s[j].a > s[i].a) continue; // } // } // } // } namespace sub5 { bool chk() { for (int i = 1; i <= n; i++) { if (s[i].b) return 0; } return 1; } int mxy[3][N]; void Main() { int mny = 2e9; for (int i = 1; i <= n; i++) { mny = min(mny, s[i].c + s[i].d); } sort(s + 1, s + n + 1, [&](node x, node y) {return x.a < y.a;}); mxy[0][n + 1] = mxy[1][n + 1] = mxy[2][n + 1] = 0; for (int i = n; i >= 1; i--) { mxy[1][i] = max(mxy[1][i + 1], s[i].c); mxy[2][i] = max(mxy[2][i + 1], s[i].d); mxy[0][i] = max(mxy[0][i + 1], mxy[1][i] + mxy[2][i]); } ll ans = (ll)s[n].a + mny; for (int i = 1; i < n; i++) { ans = min(ans, (ll)s[i].a + mxy[1][i + 1] + mxy[2][i + 1]); } printf("%lld\n", ans); } } int main() { scanf("%d", &_); while (_--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d%d%d", &s[i].a, &s[i].b, &s[i].c, &s[i].d); } if (sub1::chk()) { sub1::Main(); continue; } else if (n <= 20) { sub2::Main(); continue; } else if (n <= 100) { sub3::Main(); continue; } else if (sub5::chk()) { sub5::Main(); continue; } sub3::Main(); } return 0; }