#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// if you end up using long double, you need to set the floating point notation to fixed, and set the percision to be very high
typedef long double ld;

// contrsuct umaps like this, unordered_map<long long, int, custom_hash> safe_map;
// FIXED_RANDOM is static so it doesn not get redeclared between function calls
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
		
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


#define INF 2001001001
#define INF2 2e18
#define MOD 1000000007

#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for(long long a = b; a < c; a++)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back 
#define pf push_front
#define f first
#define s second
#define mp make_pair
#define pll pair<ll, ll>
#define pint pair<int, int>
#define tp make_tuple

// first four are north, west, east ,south
int dir1[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dir2[] = {0, 1, 0, -1, 1, -1, 1, -1};

int n;
vector<vector<int>> vec;

int find_min_quad(int a, int b);

int main() {
	// apparently this does fast i/o
	cin.tie(0) , ios::sync_with_stdio(0);
	
	// use this if you read in from a file
	/*
	freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
	*/
	
	stringstream ss;
	
	// Do it once. Do it right.
	// Read the problem statement carefully
	// Plan out the steps in words on a piece of paper before implementing
	// after RTE(obviously) but also WA, run valgrind!!!
	// Testing your solution on samples before coding is a great way to see if you read the problem correctly!!!
	// Also take notes about key elements in the problem statement while reading the problem!!!
	
	//cout << fixed << setprecision(12);
	// if you use ld, use the above and don't use string stream
	
	// use instead of ceil(a, b) if a and b are positive
	// (a + b - 1) / b
	
	int t;
	cin >> t;
	while(t > 0){
		t--;
		cin >> n;
		vec.assign(n, vector<int>());
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				int a;
				cin >> a;
				vec[i].pb(a);
			}
		}
		int minAm = vec[n/2][n/2];
		vector<int> quad_mins = {find_min_quad(0, 0), find_min_quad(0, n/2), find_min_quad(n/2, n/2), find_min_quad(n/2, 0)};
		vector<int> line_mins;
		int minTest = INF;
		for(int i = 0; i <= n/2; i++){
			minTest = min(minTest, vec[i][n/2]);
		}
		line_mins.pb(minTest);
		minTest = INF;
		for(int i = n/2; i < n; i++){
			minTest = min(minTest, vec[n/2][i]);
		}
		line_mins.pb(minTest);
		minTest = INF;
		for(int i = n/2; i < n; i++){
			minTest = min(minTest, vec[i][n/2]);
		}
		line_mins.pb(minTest);
		minTest = INF;
		for(int i = 0; i <= n/2; i++){
			minTest = min(minTest, vec[n/2][i]);
		}
		line_mins.pb(minTest);
		
		minAm = min(minAm, quad_mins[0] + quad_mins[1] + quad_mins[2] + quad_mins[3]);
		minAm = min(minAm, line_mins[0] + line_mins[2]);
		minAm = min(minAm, line_mins[1] + line_mins[3]);
		for(int i = 0; i < 4; i++){
			minAm = min(minAm, line_mins[i] + quad_mins[(i+2)%4] + quad_mins[(i+3)%4]);
		}
		cout << minAm << "\n";
	}
	cout << ss.str();
	return 0;
}

int find_min_quad(int a, int b){
	int minAm = INF;
	for(int i = a; i <= a+n/2; i++){
		for(int j = b; j <= b+n/2; j++){
			minAm = min(minAm, vec[i][j]);
		}
	}
	return minAm;
}