Winmine (지뢰찾기)

지뢰찾기(Winmine)는 윈도우에 기본으로 들어 있는 유명한 게임이다. 규칙은 간단하다. 지뢰가 없는 칸을 모두 열면 이기고, 지뢰가 있는 칸을 열면 진다.

칸을 열면 그 아래에 무엇이 있는지 드러난다. 어떤 칸은 비어 있고(주변에 지뢰가 없음), 어떤 칸에는 1부터 8까지의 숫자가 적혀 있다. 이 숫자는 그 칸과 인접한 8개 칸에 들어 있는 지뢰의 개수를 뜻한다. 비어 있는 칸(숫자 0)을 열면 인접한 빈 칸들이 연쇄적으로 함께 열린다.

Jaddy는 이 게임을 즐기지만, 가끔 논리만으로는 지뢰의 위치를 확정할 수 없는 상황에 부딪힌다. 아래 그림이 그런 예이다.

빨간 원 안의 두 칸은 어느 쪽에 지뢰가 있는지 확정할 수 없으며, 남은 지뢰 1개를 배치하는 방법이 명백히 두 가지 있다.

이런 상황에서는 추측에 의존할 수밖에 없다. 그래서 Jaddy는 현재 판의 상태를 보고, 남은 지뢰를 배치할 수 있는 서로 다른 경우의 수를 세어 주는 도구를 원한다. 그를 도와주자.

문제를 쉽게 하기 위해 입력에는 다음 두 조건이 보장된다.

1. 주어지는 판의 상태는 초기 판에서 단 한 번의 클릭으로 만들어 낼 수 있는 상태이다.
2. 아직 열리지 않은 칸들에 대해, 두 칸이 (사이의 다른 열리지 않은 칸들을 거쳐서라도) 연결되어 있다면, 이 두 칸은 이중 연결(biconnected)되어 있다. 즉, 다른 열리지 않은 칸 중 어느 하나를 제거하더라도 두 칸은 여전히 연결된 상태로 남는다. 여기서 두 칸이 연결되어 있다는 것은 변을 공유한다는 뜻이므로, 한 칸은 최대 4개의 칸과 연결된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수를 나타내는 양의 정수 $T$ ($T \le 50$)가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 세 양의 정수 $n$, $m$, $w$가 주어진다 ($1 \le n, m \le 100$, $1 \le w \le 1000$). $n$과 $m$은 각각 판의 행과 열의 수이고, $w$는 판 전체에 놓인 지뢰의 총 개수이다.

그다음 줄부터 현재 판의 상태를 나타내는 $n \times m$ 문자 격자가 주어진다. 각 문자는 다음 둘 중 하나이다.

• 숫자 0부터 8: 그 칸에 인접한 8개 칸에 들어 있는 지뢰의 개수 (0은 인접한 지뢰가 없는 빈 칸).
• . (마침표): 아직 열리지 않은 칸.

각 테스트 케이스마다 한 줄씩, Case #k: X 형식으로 출력한다. 여기서 $k$는 테스트 케이스 번호(1부터 시작)이고, $X$는 주어진 상태에서 지뢰를 배치할 수 있는 서로 다른 경우의 수를 $1000003$으로 나눈 나머지이다.