지뢰찾기 최소 클릭

지뢰찾기는 1980년대에 널리 퍼진 컴퓨터 게임이고, 지금도 일부 마이크로소프트 윈도우 운영체제에 들어 있다. 이 문제는 지뢰찾기와 규칙이 비슷하지만, 게임을 해 본 적이 없어도 풀 수 있다.

크기가 같은 칸으로 이루어진 격자에서 게임을 한다. 처음에는 모든 칸이 가려져 있다. 서로 다른 $M$개의 칸에 지뢰가 하나씩 숨어 있고, 나머지 칸에는 지뢰가 없다. 아무 칸이나 클릭해서 그 칸을 열 수 있다. 연 칸에 지뢰가 있으면 게임이 끝나고 패배한다. 지뢰가 없으면 그 칸에 0부터 8까지의 숫자가 나타나고, 이 숫자는 이웃한 칸 중 지뢰가 있는 칸의 개수다. 두 칸이 변이나 꼭짓점을 공유하면 이웃이다. 연 칸의 숫자가 0이면 그 칸의 이웃 여덟 칸도 자동으로 열리고, 새로 열린 칸의 숫자가 또 0이면 같은 과정이 재귀적으로 이어진다. 지뢰가 없는 칸을 모두 열면 게임이 끝나고 승리한다.

예를 들어 처음 판이 아래와 같다고 하자. *는 지뢰이고, c는 처음 클릭한 칸이다.

*..*...**.
....*.....
..c..*....
........*.
..........

클릭한 칸에 이웃한 지뢰가 없으므로 그 칸은 0이 되고, 이웃한 여덟 칸도 함께 열린다. 이 과정이 이어져 판은 다음과 같이 된다.

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

지뢰가 없는데 아직 열리지 않은 칸이 .으로 남아 있으므로, 게임을 이어가려면 다시 클릭해야 한다.

가능한 한 적은 클릭으로 이기려고 한다. $N \times N$ 크기의 판이 주어지면 승리에 필요한 최소 클릭 횟수를 구하라. 모든 칸에 지뢰가 있으면 열어야 할 칸이 없으므로 답은 0이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $N$이 주어진다. 다음 $N$개의 줄에는 길이가 $N$인 문자열이 한 줄에 하나씩 주어지고, 이 문자열은 처음 판을 나타낸다. 각 문자는 * 아니면 .이며, *는 지뢰가 있는 칸, .은 지뢰가 없는 칸이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 승리에 필요한 최소 클릭 횟수다.

• $1 \le T \le 100$
• $1 \le N \le 50$