#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n,m;
vector<vector<ll> >grid;
ll ans;
void check1(){
    multiset<ll> se;
    for(ll j = m;j<n;j++){
        se.insert(grid[m][j]);
    }
    for(ll i =0;i<m;i++){
        ans = min(ans , grid[m][i] + *se.begin());
        se.erase(se.find(grid[m][m + i]));
    }
}

void check2(){
    ll mi1 = grid[0][m] , mi2 = grid[m+1][m];
    for(ll i = 0;i<m;i++){
        for(ll j = m;j<n;j++){
            mi1 = min( mi1 , grid[i][j]);
            mi2 = min( mi2 , grid[i + m + 1][j]);
        }
    }
    for(ll j = 0; j < m;j++){
        ans = min(ans , grid[m][j] + mi1 + mi2 );
    }
}

void check3(){
    ll mi1 = 2e9 , mi2 = 2e9 , mi3 = 2e9 , mi4 = 2e9;
    for(ll i =0;i<m;i+=1){
        for(ll j =0 ;j<m;j+=1){
            mi1 = min(mi1, grid[i][j]);
            mi2 = min(mi2 , grid[i][j+m+1]);
            mi3 = min(mi3 , grid[i + m + 1][j]);
            mi4 = min(mi4 , grid[i + m + 1][j+m+1]);
        }
    }
    ans = min(ans , mi1 + mi2 + mi3 + mi4);
}

void trans(){
    auto grid2 = grid;
    for(ll i =0;i<n;i++){
        for(ll j =0;j<n;j++){
            grid2[j][i] = grid[i][j];
        }
    }
    swap(grid2,grid);
}

void solve(){
    cin>>n;
    grid = vector<vector<ll>> (n,vector<ll>(n));
    if(n==1){
        cout<<grid[0][0]<<endl;return;
    }
    for(ll i =0;i<n;i+=1)
        for(ll j =0;j<n;j++)
            cin>>grid[i][j];
    m = n/2;
    ans = grid[m][m];
    for(ll i =0;i<4;i++){
        trans();
        check1();check2();check3();
    }
    cout<<ans<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    ll t;cin>>t;
    while(t--)
        solve();
}