/*
	主播把赛时代码留着了。
	因为我觉得他没有错。
	四个角做一遍。
	我真的不知道为什么不对。
	虽然我赛时就不确定
*/
#include<bits/stdc++.h>
using namespace std;

// #define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fi first 
#define se second
#define spa putchar(' ')
#define ero putchar('\n')

// const int inf=1e18;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(!x)putchar('0');
    if(x<0){x=-x;putchar('-');}
    int a[300],cnt=0;
    while(x){a[++cnt]=x%10;x/=10;}
    while(cnt--){putchar(a[cnt+1]+'0');}
}

int n;
int a[5050][5050];
int b[5050][5050];
int ans;

void dfs(int x,int y,int sum,vector<int>vec){
	if(sum>=ans){
		return ;
	}
	if(y==4){
		dfs(x+1,1,sum,vec);
		return ;
	}
	if(x==4){
		if(*min_element(vec.begin(),vec.end())==1){
			ans=min(ans,sum);
		}
		return ;
	}
	dfs(x,y+1,sum,vec);
	vector<int>nxt=vec;
	if(x<=2&&y<=2) nxt[0]=1;
	if(x>=2&&y<=2) nxt[1]=1;
	if(x<=2&&y>=2) nxt[2]=1;
	if(x>=2&&y>=2) nxt[3]=1;
	dfs(x,y+1,sum+b[x][y],nxt);
}

void solve(){
    n=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=read();
        }
    }
    /*
	int ans=a[n/2+1][n/2+1];
    pii pos1={0,0};
    pii pos={0,0};
    int tmp=inf;
    for(int i=1;i<=n/2+1;i++){
        for(int j=1;j<=n/2+1;j++){
            if(tmp>a[i][j]||(tmp>=a[i][j]&&((i==n/2+1)||(j==n/2+1)))){
                tmp=a[i][j];
                pos1={i,j};
            }
        }
    }
    pii pos2={0,0};
    tmp=inf;
    for(int i=n/2+1;i<=n;i++){
        for(int j=1;j<=n/2+1;j++){
            if(tmp>a[i][j]||(tmp>=a[i][j]&&((i==n/2+1)||(j==n/2+1)))){
                tmp=a[i][j];
                pos2={i,j};
            }
        }
    }
    int ans1=0;
    if(pos1==pos2){
        ans1=a[pos1.fi][pos1.se];
    }
    else if(pos1.fi==n/2+1){
        ans1=a[pos1.fi][pos1.se];
    }
    else if(pos2.fi==n/2+1){
        ans1=a[pos2.fi][pos2.se];
    }
    else{
        ans1=a[pos1.fi][pos1.se]+a[pos2.fi][pos2.se];
    } 
    pii pos1r={0,0};
    tmp=inf;
    for(int i=1;i<=n/2+1;i++){
        for(int j=n/2+1;j<=n;j++){
            if(tmp>a[i][j]||(tmp>=a[i][j]&&((i==n/2+1)||(j==n/2+1)))){
                tmp=a[i][j];
                pos1r={i,j};
            }
        }
    }
    pii pos2r={0,0};
    tmp=inf;
    for(int i=n/2+1;i<=n;i++){
        for(int j=n/2+1;j<=n;j++){
            if(tmp>a[i][j]||(tmp>=a[i][j]&&((i==n/2+1)||(j==n/2+1)))){
                tmp=a[i][j];
                pos2r={i,j};
            }
        }
    }
    if(pos1r==pos2r){        
        if(pos2r==mkp(n/2+1,n/2+1)&&pos1==pos1r&&pos2==pos1);
        ans1+=a[pos1r.fi][pos1r.se];
    }
    else if(pos1r.fi==n/2+1){
        if(pos1r.se==n/2+1);
        ans1+=a[pos1r.fi][pos1r.se];
    }
    else if(pos2r.fi==n/2+1){
        if(pos2r.se==n/2+1);
        ans1+=a[pos2r.fi][pos2r.se];
    }
    else{
        ans1+=a[pos1r.fi][pos1r.se]+a[pos2r.fi][pos2r.se];
    }
    ans=min(ans,ans1);
    ans1=0;
    if(pos1==pos1r){
        ans1=a[pos1.fi][pos1.se];
    }
    else if(pos1.se==n/2+1){
        ans1=a[pos1.fi][pos1.se];
    }
    else if(pos1r.se==n/2+1){
        ans1=a[pos1r.fi][pos1r.se];
    }
    else{
        ans1=a[pos1.fi][pos1.se]+a[pos1r.fi][pos1r.se];
    } 
    if(pos2==pos2r){
        if(pos2r==mkp(n/2+1,n/2+1)&&pos1==pos1r&&pos2==pos1);
        ans1+=a[pos2.fi][pos2.se];
    }
    else if(pos2.se==n/2+1){
        if(pos2.se==n/2+1);
        ans1+=a[pos2.fi][pos2.se];
    }
    else if(pos2r.se==n/2+1){
        if(pos2r.se==n/2+1);
        ans1+=a[pos2r.fi][pos2r.se];
    }
    else{
        ans1+=a[pos2.fi][pos2.se]+a[pos2r.fi][pos2r.se];
    }
    ans=min(ans,ans1);
    write(ans);ero;
    return ;
	*/
	if(n==1){
		write(a[1][1]),ero;
		return;
	}
	ans=a[n/2+1][n/2+1];
	memset(b,0x3f,sizeof(b));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x=0,y=0;
			if(i<n/2+1) x=1;
			if(i==n/2+1) x=2;
			if(i>n/2+1) x=3;
			if(j<n/2+1) y=1;
			if(j==n/2+1) y=2;
			if(j>n/2+1) y=3;
			b[x][y]=min(b[x][y],a[i][j]); 
		}
	}
	dfs(1,1,0,{0,0,0,0});
	write(ans);ero;
}

signed main(){
    // freopen("distorted.in","r",stdin);
    // freopen("distorted.out","w",stdout);
    int T=read();
    while(T--){solve();}
    return 0;
}