package APS2;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class ChessRook {
static int N;
static int[][] board;
static int maxRook;
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("src\\APS2\\ChessRook_input.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
board = new int[N][N];
for (int i = 0; i < N; i++) {
String line = sc.next();
for (int j = 0; j < N; j++) {
if (line.charAt(j) == 'X') {
board[i][j] = 1; // o co tuong
}
}
}
maxRook = 0;
Solve(0, 0);
System.out.println("Case #" + tc);
System.out.println(maxRook);
} // for tc
}
public static void Solve(int row, int countRook) {
if (countRook > maxRook) {
maxRook = countRook;
// return;
}
for (int i = row; i < board.length; i++) { // dat rook theo hang
for (int j = 0; j < board[0].length; j++) {
if (isSafe(i, j)) {
board[i][j] = 2; // dat xe = 2
Solve(i, countRook + 1);
board[i][j] = 0;
}
}
}
}
static boolean isSafe(int row, int col) {
if (board[row][col] == 1 || board[row][col] == 2) { // la tuong hoc da
// co xe
return false;
}
// cung cot, hang ben tren
for (int i = row; i >= 0; i--) {
if (board[i][col] == 2) { // gap xe truoc -> false
return false;
} else if (board[i][col] == 1) { // gap tuong, break de xet tiep cac
// dieu kien sau, co kha nang
// thoa man
break;
}
}
// cung hang, cot ben trai
for (int i = col; i >= 0; i--) {
if (board[row][i] == 2) {
return false;
} else if (board[row][i] == 1) {
break;
}
}
// cung hang, cot ben phai
for (int i = col; i < board[0].length; i++) {
if (board[row][i] == 2) {
return false;
} else if (board[row][i] == 1) {
break;
}
}
return true;
}
}