#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
const int INF = (int)1e9 + 7;

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int T; cin >> T;
	while(T--)
	{
		int n; cin >> n;
		int m = n / 2;
		int A[n][n];
		for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) cin >> A[i][j];
		int a, b, c, d, e, f, g, h, i;
		a = b = c = d = e = f = g = h = INF;
		i = A[m][m];
		for(int i = 0; i <= m; ++i) for(int j = 0; j <= m; ++j) a = min(a, A[i][j]);
		for(int i = 0; i <= m; ++i) for(int j = m; j < n; ++j) b = min(b, A[i][j]);
		for(int i = m; i < n; ++i) for(int j = 0; j <= m; ++j) c = min(c, A[i][j]);
		for(int i = m; i < n; ++i) for(int j = m; j < n; ++j) d = min(d, A[i][j]);
		for(int i = 0; i <= m; ++i) e = min(e, A[i][m]);
		for(int i = 0; i <= m; ++i) f = min(f, A[m][i]);
		for(int i = m; i < n; ++i) g = min(g, A[i][m]);
		for(int i = m; i < n; ++i) h = min(h, A[m][i]);
		cout << min({ a + b + c + d, e + c + d, f + b + d, g + a + b, h + a + c, e + g, f + h, i }) << '\n';
	}
}