지뢰찾기 최소 클릭 횟수

지뢰찾기는 1980년대에 널리 퍼진 컴퓨터 게임이다. 이 문제는 같은 규칙을 쓰지만, 게임을 해 본 적이 없어도 풀 수 있다.

$N \times N$ 격자에서 게임을 한다. 모든 칸은 처음에 덮여 있고, 서로 다른 $M$개의 칸에 지뢰가 하나씩 숨어 있다. 나머지 칸에는 지뢰가 없다. 아무 칸이나 클릭해서 열 수 있다. 연 칸에 지뢰가 있으면 게임에서 진다. 지뢰가 없으면 그 칸에 0부터 8까지의 숫자가 나오는데, 이웃한 칸 중 지뢰가 있는 칸의 개수다. 두 칸이 변이나 꼭짓점을 맞대고 있으면 이웃이다. 연 칸의 숫자가 0이면 그 칸의 이웃도 모두 함께 열리고, 새로 열린 칸의 숫자가 0이면 같은 규칙이 다시 적용된다. 지뢰가 없는 칸을 모두 열면 이긴다.

예를 들어 보드가 다음과 같다고 하자. *는 지뢰이고, c는 처음 클릭한 칸이다.

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

클릭한 칸에 이웃한 지뢰가 없으므로 이 칸은 0이 되고, 이웃한 여덟 칸이 함께 열린다. 같은 규칙이 이어져 보드는 다음과 같아진다.

*..*..
11111.
00001.
00001*
111011
.*1000

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

가능한 한 적게 클릭해서 이기려고 한다. 지뢰는 한 번도 클릭하지 않는다고 할 때, 이기는 데 필요한 최소 클릭 횟수를 구하라. 모든 칸이 지뢰이면 열어야 할 칸이 없어 이미 이긴 상태이므로 답은 0이다.

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

각 테스트 케이스의 첫째 줄에는 보드의 크기 $N$이 주어진다. 이어지는 $N$개의 줄에는 길이가 $N$인 문자열이 하나씩 주어져 초기 보드를 나타낸다. 문자열은 *와 .으로만 이루어지고, *는 지뢰가 있는 칸, .은 지뢰가 없는 칸이다.

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

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