#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 { const int M = 1e3 + 9; int ind[N], m, mxa[2][N], mxb[2][N], cnt[M][M]; node _s[N]; void Main() { for (int i = 1; i <= n; i++) ind[i] = s[i].a; sort(ind + 1, ind + n + 1); m = unique(ind + 1, ind + n + 1) - ind - 1; for (int i = 1; i <= n; i++) _s[i].a = lower_bound(ind + 1, ind + m + 1, s[i].a) - ind; for (int i = 1; i <= n; i++) ind[i] = s[i].b; sort(ind + 1, ind + n + 1); m = unique(ind + 1, ind + n + 1) - ind - 1; for (int i = 1; i <= n; i++) _s[i].b = lower_bound(ind + 1, ind + m + 1, s[i].b) - ind; memset(mxa[0], 0, sizeof(int) * (n + 5)); memset(mxa[1], 0, sizeof(int) * (n + 5)); memset(mxb[0], 0, sizeof(int) * (n + 5)); memset(mxb[1], 0, sizeof(int) * (n + 5)); for (int i = 1; i <= n; i++) { mxa[0][_s[i].a] = max(mxa[0][_s[i].a], s[i].c); mxa[1][_s[i].a] = max(mxa[1][_s[i].a], s[i].d); mxb[0][_s[i].b] = max(mxb[0][_s[i].b], s[i].c); mxb[1][_s[i].b] = max(mxb[1][_s[i].b], s[i].d); } for (int i = n - 1; i >= 1; i--) { mxa[0][i] = max(mxa[0][i], mxa[0][i + 1]); mxa[1][i] = max(mxa[1][i], mxa[1][i + 1]); mxb[0][i] = max(mxb[0][i], mxb[0][i + 1]); mxb[1][i] = max(mxb[1][i], mxb[1][i + 1]); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cnt[i][j] = 0; } for (int i = 1; i <= n; i++) cnt[_s[i].a][_s[i].b]++; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1]; } } int mnx = 2e9, mny = 2e9, mxx = 0, mxy = 0; 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); mxx = max(mxx, s[i].a), mxy = max(mxy, s[i].b); } ll ans = min((ll)mxa[0][1] + mxa[1][1] + mnx, (ll)mxx + mxy + mny); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (!cnt[_s[i].a][_s[j].b] || cnt[_s[i].a][_s[j].b] == n) continue; ans = min(ans, (ll)s[i].a + s[j].b + max(mxa[0][_s[i].a + 1], mxb[0][_s[j].b + 1]) + max(mxa[1][_s[i].a + 1], mxb[1][_s[j].b + 1])); } } printf("%lld\n", ans); } } 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[0][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); } sub2::Main(); } return 0; }