#include<bits/stdc++.h>
#define ll long long
#define N 505
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0' && ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}
ll a[N][N],c[2][2],d[2][2];
void solve(){
    ll n=read();
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++)a[i][j]=read();
    }
    ll res=a[n/2+1][n/2+1];
    memset(c,0x3f,sizeof(c));memset(d,0x3f,sizeof(d));
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(i==n/2+1 || j==n/2+1){
                if(i==n/2+1){
                    if(j<=n/2)c[0][0]=min(c[0][0],a[i][j]),d[0][0]=min(d[0][0],a[i][j]),d[1][0]=min(d[1][0],a[i][j]);
                    else c[1][1]=min(c[1][1],a[i][j]),d[0][1]=min(d[0][0],a[i][j]),d[1][1]=min(d[1][0],a[i][j]);
                }
                else if(j==n/2+1){
                    if(i<=n/2)c[1][0]=min(c[1][0],a[i][j]),d[0][0]=min(d[0][0],a[i][j]),d[0][1]=min(d[1][0],a[i][j]);
                    else c[0][1]=min(c[0][1],a[i][j]),d[1][0]=min(d[0][0],a[i][j]),d[1][1]=min(d[1][0],a[i][j]);
                }
            }
            d[(i>n/2)][(j>n/2)]=min(d[(i>n/2)][(j>n/2)],a[i][j]);
        }
    }
    res=min(res,min(c[0][0]+d[0][1]+d[1][1],c[0][0]+c[1][1]));
    res=min(res,c[1][1]+d[0][0]+d[1][0]);
    res=min(res,min(c[1][0]+c[0][1],c[1][0]+d[1][0]+d[1][1]));
    res=min(res,c[0][1]+d[0][0]+d[0][1]);
    res=min(res,d[1][0]+d[0][1]+d[1][1]+d[0][0]);
    write(res);putchar('\n');
}
int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif
    ll T=read();while(T--)solve();
}