Untitled

#include<iostream>
using namespace std;

int t, n;
char map[5][5];
int vs[5][5];
int ans;

bool checksafe(int x, int y)
{
	for (int i=x-1; i>=0;i--)
	{
		if (vs[i][y] ==1) return false;
		if (vs[i][y] ==2) break;
	}
	for (int i=x+1; i<n; i++)
	{
		if (vs[i][y] ==1) return false;
		if (vs[i][y] ==2) break;
	}
	for (int j=y-1; j>=0; j--)
	{
		if (vs[x][j] ==1) return false;
		if (vs[x][j] ==2) break;
	}
	for (int j=y+1; j<n; j++)
	{
		if (vs[x][j] ==1) return false;
		if (vs[x][j] ==2) break;
	}
	return true;
}

void backtrack(int dem)
{
	
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
		{
			if (checksafe(i,j) && vs[i][j] == 0)
			{
				vs[i][j] = 1;
				backtrack(dem+1);
				vs[i][j] = 0;
			}
		}
		if (ans < dem) ans = dem;
}


int main()
{
	cin >> t;
	for (int tc = 1; tc<=t; tc++)
	{
		cin >> n;
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
			{
				cin >> map[i][j];
				vs[i][j] = 0;
				if (map[i][j] == 'X') vs[i][j] = 2;
			}

		ans = 0;
		backtrack(0);
		cout << "Case #" << tc << endl << ans << endl;
		
	}


}