#include <bits/stdc++.h>
using namespace std;
const int N = 500;
int n;
int64_t a[N][N];
int64_t mn[2][2];
int64_t mx[2];
int64_t my[2];
int64_t val[8];
unsigned msk[8] = {
    0b0001,
    0b0010,
    0b0100,
    0b1000,
    0b0011,
    0b1100,
    0b0101,
    0b1010,
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> a[i][j];
        int o = n/2;
        int id = 0;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                mn[i][j] = INT64_MAX;
                for (int x = 0; x < o; ++x) {
                    for (int y = 0; y < o; ++y) {
                        mn[i][j] = min(mn[i][j], a[i*(o+1)+x][j*(o+1)+y]);
                    }
                }
                val[id++] = mn[i][j];
            }
        }
        for (int i = 0; i < 2; ++i) {
            mx[i] = INT64_MAX;
            for (int y = 0; y < o; ++y) {
                mx[i] = min(mx[i], a[i*(o+1)+y][o]);
            }
            val[id++] = mx[i];
        }
        for (int i = 0; i < 2; ++i) {
            my[i] = INT64_MAX;
            for (int x = 0; x < o; ++x) {
                my[i] = min(my[i], a[o][i*(o+1)+x]);
            }
            val[id++] = my[i];
        }
        int64_t ans = a[o][o];
        for (int i = 0; i < 256; ++i) {
            int64_t cur = 0;
            for (int k = 0; k < 8; ++k) if ((i>>k)&1) cur += val[k];
            int vis = 0;
            for (int k = 0; k < 8; ++k) if ((i>>k)&1) vis |= msk[k];
            if (vis == 0b1111) ans = min(ans, cur);
        }
        cout << ans << '\n';
    }
    return 0;
}