회문 십자말풀이

십자말풀이는 아래에 표시된 것처럼 검은색 칸과 문자 A-Z로 이루어진 직사각형 격자이다.

십자말풀이의 단어는 문자로 이루어진 최대 수직 선분 또는 최대 수평 선분으로 정의된다. 아래 십자말풀이에서 DO와 ON는 단어의 예이다.

회문 십자말풀이는 모든 단어가 회문인 십자말풀이다. $\mathbf{R_{i,j}}$가 $i$번째 행과 $j$번째 열의 문자를 나타낸다고 하자. 여기서 $i$와 $j$는 $1$부터 번호가 매겨진다. 왼쪽 위 모서리는 $\mathbf{R_{1,1}}$이다. 아래의 회문 십자말풀이 예시에서 $\mathbf{R_{3,2}}$의 B는 $\mathbf{R_{3,1}}$에서 시작하는 가로 단어와 $\mathbf{R_{4,2}}$에서 끝나는 세로 단어 모두에 속하며, 두 단어 모두 회문이다.

$\mathbf{N}$개의 행과 $\mathbf{M}$개의 열로 이루어진 회문 십자말풀이를 선물로 받았다. 십자말풀이를 다 풀고 벽에 걸 준비를 하면서 단서를 버렸다. 하지만 실수로 문자 일부를 지워 버렸다! 십자말풀이를 최대한 많이 복원하고 싶지만, 이제 단서가 없다. 십자말풀이가 회문 십자말풀이라는 사실만을 이용하여, 주어진 십자말풀이에서 누락된 문자를 가능한 한 많이 복원하라.

아래 그림에서 누락된 문자는 비어 있는 흰색 칸으로 표시된다. 왼쪽 십자말풀이는 주어진 십자말풀이이고, 오른쪽 십자말풀이는 가능한 한 많은 문자를 복원한 결과이다. 남은 칸들은 복원하기에 충분한 정보가 없으므로 채울 수 없다.

제한

시간 제한: 60초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 주어진 입력 격자를 채워 회문 십자말풀이로 만드는 방법이 적어도 하나 존재한다. 격자의 모든 문자는 집합 $\{$A-Z, #, .$\}$에 속한다.

테스트 세트 1

$1 \le \mathbf{N},\mathbf{M} \le 50$.

테스트 세트 2

최대 10개의 케이스에 대해: $1 \le \mathbf{N},\mathbf{M} \le 1000$.

나머지 케이스에 대해: $1 \le \mathbf{N},\mathbf{M} \le 50$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 십자말풀이의 행 수와 열 수를 각각 나타내는 두 정수 $\mathbf{N}$와 $\mathbf{M}$가 주어진다. 다음 $\mathbf{N}$개의 줄은 격자의 $\mathbf{N}$개 행을 나타낸다. $i$번째 행은 $\mathbf{R_{i,1}}$, $\mathbf{R_{i,2}}$, $\dots$, $\mathbf{R_{i,M}}$를 나타내는 $\mathbf{M}$개의 문자로 이루어진다. 각 문자는 다음 중 하나이다.

• 알파벳 대문자 하나 (A-Z)

• 누락된 문자를 나타내는 마침표 하나 (.) (십자말풀이 예시의 비어 있는 흰색 칸)

• 검은색 칸을 나타내는 해시 하나 (#)

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호($1$부터 시작)이고, $y$는 채운 빈 흰색 칸의 수이다. 그런 다음 최종 격자를 나타내는 $\mathbf{N}$개의 줄을 더 출력하며, 가능한 경우 누락된 문자(.)를 알파벳 대문자(A-Z)로 대체한다.

예제 케이스 #2에서는 빈칸 중 $8$개를 채울 수 있다. 누락된 문자는 다음과 같이 채울 수 있다.

• 행 $1$, 열 $4$: 행 $1$, 열 $1$의 문자로부터 이 문자가 A임을 알 수 있다.

• 행 $2$, 열 $4 =$: 행 $1$, 열 $4$로부터 A.

• 행 $2$, 열 $6 =$: 행 $2$, 열 $4$로부터 A.

• 행 $3$, 열 $6 =$: 행 $2$, 열 $6$로부터 A.

• 행 $3$, 열 $2 =$: 행 $3$, 열 $1$로부터 B.

• 행 $4$, 열 $2 =$: 행 $3$, 열 $2$로부터 B.

• 행 $4$, 열 $3 =$: 행 $4$, 열 $2$로부터 B.

• 행 $4$, 열 $4 =$: 행 $4$, 열 $1$로부터 A.