//泥の分際で私だけの大切を奪おうだなん
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=998244353;
int qp(int x,int y)
{
	int res=1;
	for(int t=x; y; y>>=1,t=1ll*t*t%p)
		if(y&1) res=1ll*res*t%p;
	return res;
}
int a[1003][1003],f[16];
signed main()
{
	for(int T=read();T--;)
	{
		int n=read(),m=(n+1)/2;
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=n; ++j)
				a[i][j]=read();
		for(int i=0; i<16; ++i) f[i]=1e18;
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=n; ++j)
			{
				int S=0;
				if(i<=m) S+=1;
				if(i>=m) S+=2;
				if(j<=m) S+=4;
				if(j>=m) S+=8;
				f[S]=min(f[S],a[i][j]);
			}
		f[0]=0;
		for(int i=0; i<16; ++i)
			for(int j=i; j; j=i&(j-1))
				f[i]=min(f[i],f[j]+f[i-j]);
		printf("%lld\n",f[15]);
	}
	return 0;
}