#include <bits/stdc++.h>

using i64 = long long;

bool check(const std::vector<std::vector<bool>>& g) {
    for (const auto& row : g) {
        for (bool covered : row) {
            if (!covered) {
                return false;
            }
        }
    }
    return true;
}

std::tuple<i64, std::vector<std::pair<int, int>>> cal(int n, const std::vector<std::vector<int>>& a) {
    using T = std::tuple<i64, int, int>;
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;

    std::vector<std::vector<bool>> g(n, std::vector<bool>(n, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            pq.push({a[i][j], i, j});
        }
    }

    i64 tot = 0;
    std::vector<std::pair<int, int>> r;

    int rr = (n - 1) / 2;

    std::vector<std::pair<int, int>> d;
    for (int dx = -rr; dx <= rr; ++dx) {
        for (int dy = -rr; dy <= rr; ++dy) {
            d.emplace_back(dx, dy);
        }
    }

    while (!check(g)) {
        auto [cost, x, y] = pq.top();
        pq.pop();

        tot += cost;
        r.emplace_back(x, y);

        for (const auto& [dx, dy] : d) {
            int nx = x + dx;
            int ny = y + dy;
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                g[nx][ny] = true;
            }
        }
    }

    return {tot, r};
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    std::vector<std::tuple<int, std::vector<std::vector<int>>>> test;

    for (int i = 0; i < t; i++) {
        int n;
        std::cin >> n;

        std::vector<std::vector<int>> 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];
            }
        }
        test.emplace_back(n, a);
    }

    for (const auto& [n, a] : test) {
        auto [tot, r] = cal(n, a);
        tot = std::min((i64)a[n / 2][n / 2], tot);
        std::cout << tot << "\n";
    }

    return 0;
}