Untitled

package practice;

import java.io.FileInputStream;
import java.time.chrono.MinguoChronology;
import java.util.Scanner;
public class conxe {
	static int N,max,sum;
	static char[][] map;
	static int[] dichchuyenrow = {-1,0};
	static int[] dichchuyencol = {0,-1};
	static void try1(int index) {
		if(index == N *N) {
			if(max < sum) {
				max = sum;
			}
			return;
		}
		int r = index/N;
		int c = index%N;
		//DAT CON XE
		if(map[r][c] == 'X') {
			try1(index+1);
		}
		else {
			int check= 0;
			for(int i = r;i>=0 ;i--) {
				int nextr = i -1;
				int nextc = c;
				if(nextr >=0 && nextr <N && nextc>=0 && nextc <N) {
					if(map[nextr][nextc] == 'X') {
						break;
					}
					if(map[nextr][nextc] == 'D') {
						check = 1;
						break;
					}
				}
			}
			for(int i = c;i>=0 ;i--) {
				int nextr = r;
				int nextc = i-1;
				if(nextr >=0 && nextr <N && nextc>=0 && nextc <N) {
					if(map[nextr][nextc] == 'X') {
						break;
					}
					if(map[nextr][nextc] == 'D') {
						check = 1;
						break;
					}
				}
			}
			if(check == 0) {
				sum+=1;
				map[r][c] = 'D';
				try1(index+1);
				sum-=1;
				map[r][c] = '.';
				
			}
			// ko dat xe
			try1(index+1);
			
		}
		
		
	}
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/practice/input.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for(int t=1;t<=T;t++) {
			System.out.println("Case #"+t);
			N = scanner.nextInt();
			map = new char[N][N];
			for(int i =0;i<N;i++) {
				String string = scanner.next();
				for(int j =0;j<N;j++) {
					map[i][j] = string.charAt(j);
				}
						
			}
			max =0;
			try1(0);
			System.out.println(max);
			
			
	}

}
}