#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

long long r[1050][1050];
int main(){
    int t;cin>>t;while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>r[i][j];
            }
        }
        long long p1=1e18,p2=1e18,p3=1e18,p4=1e18;
        int m=n/2+1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                p1=min(p1,r[i][j]);
                p2=min(p2,r[i][j+m-1]);
                p3=min(p3,r[i+m-1][j]);
                p4=min(p4,r[i][j+m-1]);
            }
        }
        long long r1=1e18,r2=1e18,r3=1e18,r4=1e18;
        for(int i=1;i<=m;i++){
            r1=min(r1,r[i][m]);
            r2=min(r2,r[m][i]);
            r3=min(r3,r[i+m-1][m]);
            r4=min(r4,r[m][i+m-1]);
        }
        long long q=r[m][m];
        long long ans[10];
        ans[1]=q;
        ans[2]=r1+r3;
        ans[3]=r2+r4;
        ans[4]=p1+p2+r3;
        ans[5]=r1+p3+p4;
        ans[6]=r2+p2+p4;
        ans[7]=r4+p1+p3;
        ans[8]=p1+p2+p3+p4;
        ans[0]=ans[8];
        for(int i=1;i<=8;i++){
            ans[0]=min(ans[0],ans[i]);
        }
        cout<<ans[0]<<endl;
    }
}