#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int n; cin >> n;
    vector<vector<ll>> a(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    if (n == 1) {
        cout << a[0][0] << '\n';
        return;
    }

    const int w = n / 2;

    vector<ll> cost(9, LLONG_MAX);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int region = 0;
            if (i == w) region += 3;
            if (i > w) region += 6;
            if (j == w) region += 1;
            if (j > w) region += 2;

            cost[region] = min(cost[region], a[i][j]);
        }
    }

    const int corr[] = { 1, 3, 4, 5, 7 };
    const int corner[] = { 0, 2, 6, 8 };
    ll ans = LLONG_MAX;
    for (int mask = 0; mask < 32; mask++) {
        vector<bool> covered(4, false);

        ll val = 0;
        for (int bit = 0; bit < 5; bit++) {
            if (mask >> bit & 1) {
                const int region = corr[bit];
                val += cost[region];

                const int row = region / 3;
                const int col = region % 3;

                if (row <= 1 && col <= 1) covered[0] = true;
                if (row <= 1 && col >= 1) covered[1] = true;
                if (row >= 1 && col <= 1) covered[2] = true;
                if (row >= 1 && col >= 1) covered[3] = true;
            }
        }
        
        for (int corn = 0; corn < 4; corn++) {
            const int region = corr[corn];
            if (!covered[corn])
                val += cost[region];
        }

        ans = min(ans, val);
    }

    cout << ans << '\n';
}

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}