connectsolquoc

#include <iostream>

using namespace std;

int n;
int a[15][15];

struct point {
	int x, y;
};
int cur;
int oo = 2000000;
point core[15];
int max_core;
int min_ans;
int m;
int ok;
int x_cur, y_cur;
int minn(int a, int b) {
	if (a < b) return a;
	return b;
}
void backtrack(int index, int total, int chieudai) {
	if (index == cur + 1) {
		return;
	}
	if (total > max_core) {
		max_core = total;
		min_ans = chieudai;
	}
	else if (total == max_core) {
		min_ans = minn(min_ans, chieudai);
	}
	
	x_cur = core[index].x;
	y_cur = core[index].y;
	m = 0;
	ok = 1;
	// di xuong
	for (int x_next = x_cur + 1; x_next <= n; x_next++) {
		if (a[x_next][y_cur] == 1) {
			for (int k = x_cur + 1; k < x_next; k++) {
				a[k][y_cur] = 0;
			}
			ok = 0;
			break;
		}
		m++;
		a[x_next][y_cur] = 1;
		
	}
	if (ok == 1) {
		backtrack(index + 1, total + 1, chieudai + m);
		for (int x_next = x_cur + 1; x_next <= n; x_next++) {
			a[x_next][y_cur] = 0;
		}
	}
	ok = 1;
	m = 0;
	// di len
	for (int x_next = x_cur - 1; x_next >= 1; x_next--) {
		if (a[x_next][y_cur] == 1) {
			for (int k = x_next + 1; k < x_cur; k++) {
				a[k][y_cur] = 0;
			}
			ok = 0;
			break;
		}
		m++;
		a[x_next][y_cur] = 1;
	}
	if (ok == 1) {
		backtrack(index + 1, total + 1, chieudai + m);
		for (int x_next = x_cur - 1; x_next >= 1; x_next--) {
			a[x_next][y_cur] = 0;
		}
		
	}
	// sang phai
	m = 0;
	ok = 1;
	for (int y_next = y_cur + 1; y_next <= n; y_next++) {
		if (a[x_cur][y_next] == 1) {
			for (int k = y_cur + 1; k < y_next; k++) {
				a[x_cur][k] = 0;
			}
			ok = 0;
			break;	
		}
		m++
	}
}
void solve(int testcase) {
	cin >> n;
	cur = 0;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == 1 || i == n || j == 1 || j == n) {
				if (a[i][j] == 1) {
					cnt++;
				}
				continue;
			}
			if (a[i][j] == 1) {
				point tmp;
				tmp.x = i;
				tmp.y = j;
				core[++cur] = tmp;
			}
		}
	}
	
	max_core = cnt;
	min_ans = oo;
}

int main() {
	int t; cin >> t;
	
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	
	return 0;
}