#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr i64 inf = 1E18;

void chmin(i64 &a, i64 b) {
    if (a > b) {
        a = b;
    }
}

void solve() {
    int n;
    std::cin >> n;
    
    std::vector a(n, std::vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> a[i][j];
        }
    }
    
    i64 ans = inf;
    i64 lu = inf, ld = inf, ru = inf, rd = inf;
    i64 l = inf, r = inf, u = inf, d = inf;
    
    int m = n / 2;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i <= m && j <= m) {
                chmin(lu, a[i][j]);
            }
            if (i <= m && j >= m) {
                chmin(ru, a[i][j]);
            }
            if (i >= m && j <= m) {
                chmin(ld, a[i][j]);
            }
            if (i >= m && j <= m) {
                chmin(rd, a[i][j]);
            }
            if (i <= m && j == m) {
                chmin(u, a[i][j]);
            }
            if (i >= m && j == m) {
                chmin(d, a[i][j]);
            }
            if (i == m && j <= m) {
                chmin(l, a[i][j]);
            }
            if (i == m && j >= m) {
                chmin(r, a[i][j]);
            }
            if (i == m && j == m) {
                chmin(ans, a[i][j]);
            }
        }
    }
    
    chmin(ans, lu + ld + ru + rd);
    chmin(ans, l + ru + rd);
    chmin(ans, r + lu + ld);
    chmin(ans, u + ld + rd);
    chmin(ans, d + lu + ru);
    chmin(ans, l + r);
    chmin(ans, u + d);
    
    std::cout << ans << "\n";
}

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