#1014 Bishop

57  5 s   128 MB  

Description

N 의 체스판에 Queen이 서로 공격하지 않도록 놓을 수 있는 방법을 찾아라.

위 문제는 유명한 N-Queen 문제이다. 자료구조 시간에 N-Queen 문제를 풀면서 백트래킹을 마스터했다고 생각한 LIBe는 보다 더 어려운 문제를 풀어보기 위해서 문제를 다음과 같이 변경하였다.

체스판에 장애물들이 있고, Queen이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Queen의 개수는 몇 개일까?

그러나 세상의 모든 일은 생각대로 되지 않는 법. 코딩 스킬이 부족했던 LIBe는 위 문제를 풀다가 포기하고 결국 문제를 다음과 같이 변경하였다.

체스판에 장애물들이 있고, Bishop이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Bishop의 개수는 몇 개일까?

LIBe는 과연 이 문제를 풀 수 있을까?

Input

입력은 여러 개의 테스트 케이스로 주어진다. 입력의 첫 줄에는 테스트 케이스의 개수 $T$ $(1 \leq T \leq 100)$가 들어온다.

각각의 테스트 케이스의 첫 줄에는 체스판의 크기 $N$ $(1 \leq N \leq 8)$이 주어진다. 이후 $N$ 줄에는 체스판의 상태가 주어진다. .은 Bishop을 놓을 수 있는 곳이며, *은 장애물이다.

Output

각각의 테스트 케이스들에 대해 최대로 놓을 수 있는 Bishop의 개수를 출력한다.

Sample Input

Sample Output

2
5
.....
.....
.....
.....
.....
8
..**.*.*
**.***.*
*.**...*
.*.**.**
*.**.*.*
..**.*.*
...*.*.*
**.*.*.*
8
18

Source

2009 Ajou University Programming Contest