#include<bits/stdc++.h>
#define int long long 
using namespace std;
int a[505][505];
int val[10];
const int inf=0x3f3f3f3f3f3f3f3f;
void test()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	int m=n/2;
	for(int i=1;i<10;i++)
		val[i]=inf;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			int x=(i<=m)+(i<=m+1),y=1+(j<=m)+(j<=m+1);
			val[3*x+y]=min(val[3*x+y],a[i][j]);
		}
	val[2]=min(val[2],val[1]+val[3]);
	val[4]=min(val[4],val[1]+val[7]);
	val[6]=min(val[6],val[3]+val[9]);
	val[8]=min(val[8],val[7]+val[9]);
	val[5]=min({val[5],val[2]+val[8],val[4]+val[6],val[1]+val[6]+val[8],val[3]+val[4]+val[8],val[7]+val[2]+val[6],val[9]+val[2]+val[4]});
	cout<<val[5]<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
		test();
}
/*
2
3
1 1 1
1 1 1
1 1 1
5
8 5 2 8 3
5 6 9 7 3
7 8 9 1 4
8 9 4 5 5
2 8 6 9 3
*/