#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 1e5 + 5;
vector <int> g[14 * N];
int val[14 * N], comp[14 * N], tt;
int info[N * 12], cur, cnt;
inline void either(int f, int j) {
    f = max(2*f, -1-2*f);
    j = max(2*j, -1-2*j);
    g[f].push_back(j^1);
    g[j].push_back(f^1);
    if (tt) {
        info[cur++] = f;
        info[cur++] = j;
    }
}
inline void clr() {
    for (int i = 0; i < 2 * cnt; ++i) {
        g[i].clear();
    }
}
vector <int> z;
int tme = 0;
int dfs(int i) {
    int low = val[i] = ++tme, x; z.push_back(i);
    for(int e : g[i]) if (!comp[e])
        low = min(low, val[e] ?: dfs(e));
    if (low == val[i]) do {
        x = z.back(); z.pop_back();
        comp[x] = low;
    } while (x != i);
    return val[i] = low;
}
inline bool solvet() {
    for (int i = 0; i < 2 * cnt; ++i) 
        comp[i] = val[i] = 0;
    for (int i = 0; i < 2 * cnt; ++i) {
        if (!comp[i]) dfs(i);
    }
    for (int i = 0; i < cnt; ++i) {
        if (comp[2*i] == comp[2*i+1]) return 0;
    }
    return 1;
}
int nos[3][2 * N], ind[3][N], _ind[3][N];
int n, a[N][3], _a[N][3], d[N], _d[N];
vector <int> vals[3];
inline bool can(int x) {
	for (int j = 0; j < 3; ++j) {
		int r = -1, r2 = -1;
		for (int _i = 0; _i < n; ++_i) {
			int i = ind[j][_i];
			while (r + 1 < sz(vals[j]) && vals[j][r + 1] <= a[i][j] + x)
				++r;
			if (r + 1 < sz(vals[j])) {
				tt++;
				either(~d[i], nos[j][r + 1]);
			}
            i = _ind[j][_i];
			while (r2 + 1 < sz(vals[j]) && vals[j][r2 + 1] <= _a[i][j] + x)
				++r2;
			if (r2 + 1 < sz(vals[j])) {
				++tt;
				either(d[i], nos[j][r2 + 1]);
			}
		}
	}
    bool res = solvet();
    while (tt > 0) {
		g[info[--cur]].pop_back();
        g[info[--cur]].pop_back();
        tt--;
	}
	return res;
}
inline void solve() {
	cin >> n;
	for (int j = 0; j < 3; ++j)
		vals[j].clear();    
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> a[i][j];
			vals[j].pb(a[i][j]);
		}
		for (int j = 0; j < 3; ++j) {
			cin >> _a[i][j];
            vals[j].pb(_a[i][j]);
		}
	}
	for (int j = 0; j < 3; ++j) {
		sort(all(vals[j]));
		for (int i = 0; i < n; ++i)
			ind[j][i] = _ind[j][i] = i + 1;
		sort(ind[j], ind[j] + n, [&] (int x, int y) {
			return a[x][j] < a[y][j];
		});
		sort(_ind[j], _ind[j] + n, [&] (int x, int y) {
			return _a[x][j] < _a[y][j];
		});
	}
    clr();
    cnt = 0;
    for (int j = 0; j < 3; ++j) {
		for (int i = 0; i < sz(vals[j]); ++i)
			nos[j][i] = ++cnt;
	}
	for (int i = 1; i <= n; ++i) 
		d[i] = ++cnt;
    ++cnt;
	for (int j = 0; j < 3; ++j) {
		int v = 0;
		for (int _i = 0; _i < n; ++_i) {
			int i = ind[j][_i];
			while (v < sz(vals[j]) && vals[j][v] < a[i][j])
				++v;
			either(~d[i], ~nos[j][v]);
		}
		v = 0;
		for (int _i = 0; _i < n; ++_i) {
			int i = _ind[j][_i];
			while (v < sz(vals[j]) && vals[j][v] < _a[i][j])
				++v;
			either(d[i], ~nos[j][v]);
		}
	}
	for (int j = 0; j < 3; ++j) {
		for (int i = 0; i + 1 < sz(vals[j]); ++i)
			either(~nos[j][i], nos[j][i + 1]);
	}
	int l = 0, r = 1e7, ans = 1e9;
	while (r >= l) {
		int m = (l + r) / 2;
		if (can(m))
			ans = m, r = m - 1;
		else
			l = m + 1;
	}
    cout << ans << '\n';
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
    int T;
	cin >> T;
	while (T--) {
        solve();
	}
	return 0;
}