지뢰 찾기

지뢰 찾기는 1980년대에 인기를 얻은 컴퓨터 게임으로, 지금도 Microsoft Windows 운영 체제의 일부 버전에 포함되어 있다. 이 문제는 비슷한 발상을 사용하지만, 지뢰 찾기를 해 본 적이 있다고 가정하지 않는다.

이 문제에서는 동일한 칸으로 이루어진 격자에서 게임을 한다. 각 칸의 내용은 처음에는 숨겨져 있다. 격자의 서로 다른 M개 칸에 M개의 지뢰가 숨겨져 있다. 다른 칸에는 지뢰가 없다. 아무 칸이나 클릭하여 그 내용을 드러낼 수 있다. 드러난 칸에 지뢰가 있으면 게임이 끝나고 패배한다. 그렇지 않으면 드러난 칸에는 0 이상 8 이하의 숫자가 표시되며, 이는 지뢰가 있는 이웃 칸의 수를 나타낸다. 두 칸이 모서리 또는 변을 공유하면 이웃이다. 또한 드러난 칸에 0이 표시되면, 드러난 칸의 모든 이웃도 재귀적으로 자동으로 드러난다. 지뢰가 없는 모든 칸이 드러나면 게임이 끝나고 승리한다.

예를 들어, 보드의 초기 상태는 다음과 같을 수 있다('*'는 지뢰를 나타내고, 'c'는 처음 클릭한 칸이다):

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

클릭한 칸에 인접한 지뢰가 없으므로, 이 칸이 드러나면 0이 되고 인접한 8개 칸도 함께 드러난다. 이 과정이 계속되어 다음과 같은 보드가 된다:

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

이 시점에도 지뢰가 없으면서 아직 드러나지 않은 칸('.' 문자로 표시됨)이 있으므로, 게임을 계속하려면 플레이어가 다시 클릭해야 한다.

가능한 한 빨리 게임에서 승리하려고 한다. 게임에서 승리하는 데 필요한 최소 클릭 횟수를 구하려고 한다. 보드의 크기(N x N)가 주어지면, 이 최소 클릭 횟수를 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (Test Set 1 - 공개)

1 ≤ N ≤ 50.

큰 데이터 세트 (Test Set 2 - 비공개)

1 ≤ N ≤ 300.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 정수 N 하나가 주어진다. 이어지는 N개의 줄에는 길이가 N이고 '*'와 '.'으로 구성된 문자열이 주어지며, 지뢰 찾기 보드의 초기 상태를 나타낸다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 승리하는 데 필요한 최소 클릭 횟수이다.