#include <bits/stdc++.h>
#define N 504
#define INF 1000000000000000000
using namespace std;
typedef long long ll;

int T, n;
ll mx[N][N], a[N][N], prer[N], sufr[N], prec[N], sufc[N];

void clr ()
{
	for (int i=0; i<=n+1; i++) {
		for (int j=0; j<=n+1; j++) {
			mx[i][j]=INF;
		}
	}
    prer[0]=INF; sufr[n+1]=INF;
    prec[0]=INF; sufc[n+1]=INF;
}

int main ()
{
//	freopen("0test.in", "r", stdin);
//	freopen("0test.out", "w", stdout);
	
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				scanf("%d", &a[i][j]);
			}
		}

        clr();

        int len=(n/2);

        ll res1=0, ans=INF;

        for (int i=1; i<=n; i++) {
        	prer[i]=min(prer[i-1], a[len+1][i]);
		}
		for (int i=n; i>=1; i--) {
        	sufr[i]=min(sufr[i+1], a[len+1][i]);
		}
        for (int i=1; i<=n; i++) {
        	prec[i]=min(prec[i-1], a[i][len+1]);
		}
		for (int i=n; i>=1; i--) {
        	sufc[i]=min(sufc[i+1], a[i][len+1]);
		}

        ans=min(ans, prer[len+1]+sufr[len+1]);
        ans=min(ans, prec[len+1]+sufc[len+1]);
		
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
                mx[i][j]=min(a[i][j], min(mx[i-1][j], mx[i][j-1]));
			}
		}
        res1+=mx[len+1][len+1];
        ans=min(ans, mx[len+1][len+1]+sufr[len+1]+sufc[len+1]);

        for (int i=n; i>=1; i--) {
            for (int j=1; j<=n; j++) {
                mx[i][j]=min(a[i][j], min(mx[i+1][j], mx[i][j-1]));
            }
        }
        res1+=mx[len+1][len+1];
        ans=min(ans, mx[len+1][len+1]+sufr[len+1]+prec[len+1]);

        for (int i=1; i<=n; i++) {
			for (int j=n; j>=1; j--) {
                mx[i][j]=min(a[i][j], min(mx[i-1][j], mx[i][j+1]));
			}
		}
        res1+=mx[len+1][len+1];
        ans=min(ans, mx[len+1][len+1]+prer[len+1]+sufc[len+1]);

        for (int i=n; i>=1; i--) {
            for (int j=n; j>=1; j--) {
                mx[i][j]=min(a[i][j], min(mx[i+1][j], mx[i][j+1]));
            }
        }
        res1+=mx[len+1][len+1];
        ans=min(ans, mx[len+1][len+1]+prer[len+1]+prec[len+1]);
        
        ans=min(ans, res1);
        
        ans=min(ans, a[len+1][len+1]);

        printf("%lld\n", ans);
	} 
	
    return 0;
}