#include <bits/stdc++.h>
#define dd(x) cout << #x << "\n"
#define d(x) cout << #x  << ": " << x << "\n"
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
const int inf = 0x3f3f3f3f3f3f3f3fLL;

void solve() {
    int n; cin >> n;
    int c = n / 2 + 1;
    vector grid(n + 1, vector<int> (n + 1));

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> grid[i][j];
        }
    }

    array<pair<int, int>, 9> rep;
    rep.fill({inf, 0});
    

    int ans = grid[c][c];
    // d(ans);
    
    auto build = [&](int s1, int e1, int s2, int e2, int id, int st) -> void {
        for(int i = s1; i <= e1; i++) {
            for(int j = s2; j <= e2; j++) {
                rep[id].first = min(rep[id].first, grid[i][j]);
            }
        }
        rep[id].second = st;
    };

    build(1, c - 1, 1, c - 1, 0, 8);
    build(1, c - 1, c + 1, n, 1, 4);
    build(c + 1, n, 1, c - 1, 3, 1);
    build(c + 1, n, c + 1, n, 2, 2);

    for(int i = 1; i <= c - 1; i++) {
        rep[4].first = min(rep[4].first, grid[i][c]);
    }
    rep[4].second = 12;

    for(int i = c + 1; i <= n; i++) {
        rep[5].first = min(rep[5].first, grid[i][c]);
    }
    rep[5].second = 3;

    for(int i = 1; i <= c - 1; i++) {
        rep[6].first = min(rep[6].first, grid[c][i]);
    }
    rep[6].second = 9;

    for(int i = c + 1; i <= n; i++) {
        rep[7].first = min(rep[7].first, grid[c][i]);
    }
    rep[7].second = 6;

    // for(int i = 0; i <= 7; i++) {
    //     d(i); d(rep[i].first);
    // }

    
    for(int i = (1 << 8) - 1; ~i; i--) {
        int res = 0, st = 0;
        for(int j = 7; ~j; j--) {
            if(i & (1 << j)) {
                res += rep[j].first;
                st |= rep[j].second;
            }
        }
        if(st == 15) ans = min(ans, res);
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

/*

2
3
1 1 1
1 1 1
1 1 1
5
8 5 2 8 3
5 6 9 7 3
7 8 9 1 4
8 9 4 5 5
2 8 6 9 3

*/