Untitled

#include<iostream>
using namespace std;
char M[4][4];
int N;
int ans =0;
bool check(int r,int c)
{
	if(M[r][c] == 'X') { return false;}
	for(int i=c-1; i>=0; i--)
	{
		if(M[r][i] == 'C') {return false;}
		if(M[r][i] == 'X') {break;}
	}
	for(int i=r-1; i>=0; i--)
	{
		if(M[i][c] == 'C') {return false;}
		if(M[i][c] == 'X') {break;}
	}
	return true;
}
void backtrack(int k)
{
	if(k == N*N) {
		int count_ =0;
		for(int i=0; i<N; i++)
		{
			for(int j=0; j< N; j++)
			{
				if(M[i][j] == 'C') { count_ ++;}
			}
		}
		if(count_ > ans ) { ans = count_;}
		return ;
	}
	if(check(k/N,k%N))
	{
		for(int i=0; i<2; i++)
		{
         if(i==0) backtrack(k+1);
		 else{
			 M[k/N][k%N] = 'C';
			 backtrack(k+1);
			 M[k/N][k%N] = '.';
		 }
		}
	}
	else backtrack(k+1);


}
int main()
{
	int t;
	cin >> t;
	for(int stt=1; stt <=t; stt ++)
	{
		cin >> N;
		for(int i=0; i<N; i++)
		{
			for(int j=0; j<N; j++)
			{
				cin >> M[i][j];
			}
		}
		///////////////////
		backtrack(0);
		cout << "Case #" << stt << endl << ans << endl;
		ans =0;
	}
}