Untitled

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class RookProblem {
    static int[][] board = new int[5][5];
    static boolean[][] visited = new boolean[5][5];
    static int count = 0;
    static int max = 0;
    static int n;

    static boolean isSafe(int row, int col) {
        if (board[row][col] == 1) {
            return false;
        }
        // Check the row
        for (int x = 0; x < col; x++) {
            if (board[row][x] == 1) {
                return false;
            }
        }
        // Check the column
        for (int x = col; x < n; x++) {
            if (board[row][x] == 1) {
                return false;
            }
        }
        // Check above the current cell
        for (int i = row; i >= 0; i--) {
            if (board[i][col] == 1) {
                return false;
            }
        }
        return true;
    }

    static void solveBoard(int pos) {
        if (pos == n * n) {
            if (count > max) {
                max = count;
            }
            return;
        }

        int x = pos / n;
        int y = pos % n;
        if (isSafe(x, y)) {
            visited[x][y] = true;
            count++;
        }
        solveBoard(pos + 1);
        if (visited[x][y]) {
            visited[x][y] = false;
            count--;
        }
        solveBoard(pos + 1);
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("Text"));
        Scanner scanner = new Scanner(System.in);
        int tc = scanner.nextInt();
        for (int Case = 1; Case <= tc; Case++) {
            n = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                String s = scanner.next();
                for (int j = 0; j < n; j++) {
                    if (s.charAt(j) == '.') {
                        board[i][j] = 0;
                    } else {
                        board[i][j] = 1;
                    }
                }
            }

            count = 0;
            max = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    visited[i][j] = false;
                }
            }
            solveBoard(0);

            System.out.println(max);
        }
    }
}


import java.util.Scanner;

public class Main {
    static int maxRooks = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();
        for (int t = 0; t < testCases; t++) {
            int N = scanner.nextInt();
            char[][] board = new char[N][N];
            scanner.nextLine(); // Consume the newline after N

            for (int i = 0; i < N; i++) {
                String row = scanner.nextLine();
                board[i] = row.toCharArray();
            }

            int maxRooks = maxRooks(board);
            System.out.println("Case #" + (t + 1));
            System.out.println(maxRooks);
        }
    }

    private static int maxRooks(char[][] board) {
        maxRooks = 0;
        backtrack(board, 0, 0, 0);
        return maxRooks;
    }

    private static void backtrack(char[][] board, int row, int col, int rookCount) {
        if (row == board.length) {
            maxRooks = Math.max(maxRooks, rookCount);
            return;
        }

        int nextRow = (col == board[row].length - 1) ? (row + 1) : row;
        int nextCol = (col == board[row].length - 1) ? 0 : col + 1;

        if (board[row][col] == '.') {
            // Check if it's safe to place a rook in this cell
            boolean safe = true;
            for (int i = 0; i < row; i++) {
                if (board[i][col] == 'R') {
                    safe = false;
                    break;
                }
            }
            for (int j = 0; j < col; j++) {
                if (board[row][j] == 'R') {
                    safe = false;
                    break;
                }
            }

            if (safe) {
                board[row][col] = 'R';
                backtrack(board, nextRow, nextCol, rookCount + 1);
                board[row][col] = '.';
            }
        }

        // Continue without placing a rook in this cell
        backtrack(board, nextRow, nextCol, rookCount);
    }
}