Untitled

// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

using namespace std;
int const max_size =15;
int map[15][15];
int core[max_size][2];
int n, cntCore;
int ans, maxCore;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
int go(int cores, int h){
	int len=0;
	int tempX= core[cores][0]+dx[h];
	int tempY= core[cores][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 cores , int h){
	int tempX= core[cores][0]+dx[h];
	int tempY= core[cores][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(int argc, char** argv)
{
	int test_case;
	int T;


	freopen("text.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin>>n;
		 cntCore=0;
		for(int i=0; i<n;i++){
			for(int j=0 ; j<n; j++){
				cin>>map[i][j];
				if(map[i][j]==1){
					core[cntCore][0]=i;
					core[cntCore][1]=j;
					cntCore++;
				}

			}

		}
		maxCore=0;
		ans=100000;
		Try(0,0,0);


		cout << "#" << test_case << " " << ans << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}