#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=505;
int T,n,m,a[N][N];LL f[55],g[55],h[55];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
	while(T--)
	{
		cin>>n;m=n/2+1;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
		memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));g[0]=0;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		{
			int s=0;
			if(i<=m&&j<=m) s|=1;
			if(i<=m&&j>=m) s|=2;
			if(i>=m&&j<=m) s|=4;
			if(i>=m&&j>=m) s|=8;
			for(int t=0;t<16;t++) if((t&s)==t) f[t]=min(f[t],(LL)a[i][j]);
		}
		for(int i=1;i<16;i++)
		{
			memcpy(h,g,sizeof(g));
			for(int j=0;j<16;j++) if((i&j)==0) g[i|j]=min(g[i|j],h[j]+f[i]);
		}cout<<g[15]<<"\n";
	}
	return 0;
}