#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> a;

int getmin(int l, int r, int u, int d) {
    int res = 1 << 30;
    for (int i = l; i < r; i++) {
        for (int j = u; j < d; j++) {
            res = min(res, a[j][i]);
        }
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(n);
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    if (n == 1) {
        cout << a[0][0] << endl;
        return;
    }
    int q1 = getmin(0, n / 2, 0, n / 2);
    int q2 = getmin(n / 2 + 1, n, 0, n / 2);
    int q3 = getmin(0, n / 2, n / 2 + 1, n);
    int q4 = getmin(n / 2 + 1, n, n / 2 + 1, n);

    int m1 = getmin(n / 2, n / 2 + 1, 0, n / 2);
    int m2 = getmin(0, n / 2, n / 2, n / 2 + 1);
    int m3 = getmin(n / 2, n / 2 + 1, n / 2 + 1, n);
    int m4 = getmin(n / 2 + 1, n, n / 2, n / 2 + 1);

    int q = a[n / 2][n / 2];

    int upmin = min(min(q1, m2) + min(q2, m4), m1);
    int dwmin = min(min(q3, m2) + min(q4, m4), m3);
    int lmin = min(min(q1, m1) + min(q3, m3), m2);
    int rmin = min(min(q2, m2) + min(q4, m3), m4);

    int ans = min(a[n / 2][n / 2], min(upmin + dwmin, lmin + rmin));
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t > 0) {
        t--;
        solve();
    }
}