Untitled

#include<iostream>

using namespace std;
int N,cntCore;
int map[15][15];
int cores[15][2];
int maxCore;
int ans;
int dx[4]={-1, 0, 0, 1};
int dy[4]={0, -1,1, 0};
void nhap()
{
	for(int i=0;i<N;i++){
		for(int j=0; j<N;j++){
			cin>>map[i][j];
		}

	}

}

int  go(int core, int h){
	int len =0;
	int tempX= cores[core][0] + dx[h];
	int tempY= cores[core][1] + dy[h];
	while(tempX >=0 && tempX < N && tempY >=0 && tempY < N){
			map[tempX][tempY]= 1-map[tempX][tempY];
			len++;
			tempX +=dx[h];
			tempY += dy[h];
	}
	return len;
}

bool check(int core, int h){
	int len =0;
	int tempX= cores[core][0] + dx[h];
	int tempY= cores[core][1] + dy[h];
	while(tempX >=0 && tempX < N && tempY >=0 && tempY < N){
			if(map[tempX][tempY] ==1) return false;
			tempX +=dx[h];
			tempY += dy[h];
	}
	return true;
}

void Try(int tempcore, int corenum, int wireLen){
	if(tempcore == cntCore){
		if(corenum > maxCore){
			maxCore=corenum;
			ans = wireLen;
		}
		else if(corenum == maxCore && wireLen < ans) ans = wireLen;
		return;
	}
	bool flag = true;
	for(int h = 0; h < 4; h++){
		if(check(tempcore,h)){
			flag =false;
			int len = go(tempcore, h);
			Try(tempcore+1, corenum+1, wireLen +len);
			go(tempcore, h);
		}
	}
	if(flag) Try(tempcore+1, corenum, wireLen);
	
}



int main(){
	freopen("text.txt", "r", stdin);
	int T;
	cin >> T;
	for(int test_case = 1; test_case <= T; test_case++)
	{
		cin>>N;
		nhap();
		cntCore =0;
		for(int i = 1; i < N-1; i++){
			for(int j = 1; j < N-1; j++){
				if(map[i][j] == 1){
					cores[cntCore][0]=i;
					cores[cntCore][1]=j;
					cntCore++;
				}
			}
		}
		ans =1000000;
		maxCore =0;
		Try(0,0,0);
		cout << "#" << test_case << " " << ans << endl;
	}
	return 0;
}