#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int Read()
{
	int Output=0;
	char Input=getchar();
	while(Input<'0'||Input>'9')
	Input=getchar();
	while(Input>='0'&&Input<='9')
	{
		Output=Output*10+Input-'0';
		Input=getchar();
	}
	return Output;
}
int T;
int N;
int A[501][501];
int Vis[501][501];
struct point
{
	int X,Y;
}Four[11];
ll Answer;
point Search(int Xa,int Ya,int Xb,int Yb)
{
	point Ans=(point){Xa,Ya};
	for(int i=Xa;i<=Xb;++i)
	{
		for(int j=Ya;j<=Yb;++j)
		{
			if(A[i][j]<A[Ans.X][Ans.Y])
			Ans=(point){i,j};
		}
	}
	return Ans;
}
bool Check()
{
	for(int i=1;i<=N;++i)
	for(int j=1;j<=N;++j)
	if(!Vis[i][j])
	return false;
	return true;
}
void DFS(int Deep,ll Val)
{
	if(Deep==10)
	{
		if(Check())
		Answer=min(Answer,Val);
		return;
	}
	for(int i=max(Four[Deep].X-(N>>1),1);i<=min(Four[Deep].X+(N>>1),N);++i)
	for(int j=max(Four[Deep].Y-(N>>1),1);j<=min(Four[Deep].Y+(N>>1),N);++j)
	++Vis[i][j];
	DFS(Deep+1,Val+A[Four[Deep].X][Four[Deep].Y]);
	for(int i=max(Four[Deep].X-(N>>1),1);i<=min(Four[Deep].X+(N>>1),N);++i)
	for(int j=max(Four[Deep].Y-(N>>1),1);j<=min(Four[Deep].Y+(N>>1),N);++j)
	--Vis[i][j];
	DFS(Deep+1,Val);
}
int main()
{
	T=Read();
	while(T--)
	{
		Answer=1e15;
		N=Read();
		if(N==1)
		{
			printf("%d\n",Read());
			continue;
		}
		for(int i=1;i<=N;++i)
		{
			for(int j=1;j<=N;++j)
			{
				A[i][j]=Read();
			}
		}
		Four[1]=Search(1,1,(N>>1)+1,(N>>1)+1);
		Four[2]=Search(1,(N>>1)+1,(N>>1)+1,N);
		Four[3]=Search((N>>1)+1,1,N,(N>>1)+1);
		Four[4]=Search((N>>1)+1,(N>>1)+1,N,N);
		Four[5]=(point){(N>>1)+1,(N>>1)+1};
		Four[6]=Search((N>>1)+1,1,(N>>1)+1,(N>>1)+1);
		Four[7]=Search((N>>1)+1,(N>>1)+1,(N>>1)+1,N);
		Four[8]=Search(1,(N>>1)+1,(N>>1)+1,(N>>1)+1);
		Four[9]=Search((N>>1)+1,(N>>1)+1,(N>>1)+1,N);
		DFS(1,0);
		printf("%lld\n",Answer);
	}
}