#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cerr << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

void solve() {
    int n; cin >> n;
    vector<vector<ll>> a(n, vector<ll>(n));
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j) 
            cin >> a[i][j];
    ll ans = a[n / 2][n / 2];
    if (n == 1) return cout << ans << el, void();
    vector<ll> x, y;
    for (int i = 0; i < n; ++i) x.emplace_back(a[n / 2][i]), y.emplace_back(a[i][n / 2]);
    sort(x.begin(), x.end()), sort(y.begin(), y.end());
    ans = min({ans, x[0] + x[1], y[0] + y[1]});
    vector<vector<ll>> b(2, vector<ll>(2, INF));
    for (int i = 0; i < n / 2; ++i) 
        for (int j = 0; j < n / 2; ++j) 
            for (int x = 0; x < 2; ++x) 
                for (int y = 0; y < 2; ++y) 
                    b[x][y] = min(b[x][y], a[i + n / 2 * x][j + n / 2 * y]);
    ans = min(ans, b[0][0] + b[0][1] + b[1][0] + b[1][1]);
    for (int i = 0; i < n; ++i) {
        if (i < n / 2) {
            ans = min(ans, a[i][n / 2] + b[1][0] + b[1][1]);
            ans = min(ans, a[n / 2][i] + b[0][1] + b[1][1]);
        } else {
            ans = min(ans, a[i][n / 2] + b[0][0] + b[0][1]);
            ans = min(ans, a[n / 2][i] + b[0][0] + b[1][0]);
        }
    }
    cout << ans << el;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}