Untitled

package backtrack;

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

public class rook {
	static int arr[][] = new int[5][5];

	static boolean visit[][] = new boolean[5][5];
	static int count = 0;
	static int max = 0;
	static int n;

	static boolean isSafe(int row, int col) {
		boolean check = true;
		if (arr[row][col] == 1) {
			check = false;
		}
		for (int x = 0; x < col; x++) {
			if (arr[row][x] == 1) {
				break;
			}
			if (visit[row][x] == true)
				check = false;

		}
		for (int x = col; x < n; x++) {
			if (arr[row][x] == 1) {
				break;
			}
			if (visit[row][x] == true)
				check = false;

		}
		for (int i = row; i < n; i++) {
			if (arr[i][col] == 1) {
				break;
			}
			if (visit[i][col] == true)
				check = false;

		}
		for (int i = row; i >= 0; i--) {
			if (arr[i][col] == 1) {
				break;
			}
			if (visit[i][col] == true)
				check = false;

		}
		return check;
	}

	static void solveCol(int[][] board, int pos) {

		if (pos == n * n) {
			if (count > max) {
				max = count;
	
			}
		}
		int x = pos / n;
		int y = pos % n;
		if (isSafe(x, y)) {
			visit[x][y] = true;
			count += 1;
		}
		solveCol(board, 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) == '.') {
						arr[i][j] = 0;
					} else {
						arr[i][j] = 1;
					}
				}
			}

			count = 0;
			max = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					visit[i][j] = false;
				}
			}
			solveCol(arr, 0);

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