Untitled

///tttt

#include <iostream>

using namespace std;

const int MAX_N = 4;

int N;
char board[MAX_N][MAX_N];
int maxRooks; // Biến lưu trữ kết quả số lượng Rook tối đa
bool rowOccupied[MAX_N]; // Đánh dấu hàng đã bị chiếm
bool colOccupied[MAX_N]; // Đánh dấu cột đã bị chiếm

bool isSafe(int row, int col) {
    if (rowOccupied[row] || colOccupied[col]) {
        return false;
    }

    // Kiểm tra các ô trên cùng hàng và cột từ [0 đến col-1] và [row-1 đến 0] có tường 'X' không
    for (int i = col - 1; i >= 0; i--) {
        if (board[row][i] == 'X') break;
        if (colOccupied[i]) return false;
    }

    for (int i = row - 1; i >= 0; i--) {
        if (board[i][col] == 'X') break;
        if (rowOccupied[i]) return false;
    }

    return true;
}

void backtrack(int placedRooks, int row) {
    if (row == N) {
        if (placedRooks > maxRooks) {
            maxRooks = placedRooks;
        }
        return;
    }

    for (int col = 0; col < N; col++) {
        if (board[row][col] == '.' && isSafe(row, col)) {
            // Đặt Rook
            rowOccupied[row] = true;
            colOccupied[col] = true;
            backtrack(placedRooks + 1, row + 1);
            // Gỡ Rook
            rowOccupied[row] = false;
            colOccupied[col] = false;
        }
    }

    // Không đặt Rook ở dòng này, chuyển sang dòng tiếp theo
    backtrack(placedRooks, row + 1);
}

int main() {
    int T;
    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 >> board[i][j];
            }
        }

        maxRooks = 0;
        for (int i = 0; i < N; i++) {
            rowOccupied[i] = false;
            colOccupied[i] = false;
        }

        backtrack(0, 0);

        cout << "Case #" << tc << endl << maxRooks << endl;
    }

    return 0;
}