Untitled

//test1208

#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 rows[MAX_N][MAX_N];
bool cols[MAX_N][MAX_N];

bool isSafe(int row, int col) {
    // Kiểm tra hàng
    for (int i = col - 1; i >= 0; i--) {
        if (board[row][i] == 'X') break;
        if (rows[row][i]) return false;
    }
    for (int i = col + 1; i < N; i++) {
        if (board[row][i] == 'X') break;
        if (rows[row][i]) return false;
    }

    // Kiểm tra cột
    for (int i = row - 1; i >= 0; i--) {
        if (board[i][col] == 'X') break;
        if (cols[i][col]) return false;
    }
    for (int i = row + 1; i < N; i++) {
        if (board[i][col] == 'X') break;
        if (cols[i][col]) 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
            rows[row][col] = true;
            cols[row][col] = true;
            backtrack(placedRooks + 1, row + 1);
            // Gỡ Rook
            rows[row][col] = false;
            cols[row][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 < MAX_N; i++) {
            for (int j = 0; j < MAX_N; j++) {
                rows[i][j] = false;
                cols[i][j] = false;
            }
        }

        backtrack(0, 0);

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

    return 0;
}