회문 십자말풀이

십자말풀이는 아래 그림처럼 검은 칸과 A-Z 글자로 이루어진 직사각형 격자다.

십자말풀이에서 단어는 가로 또는 세로로 연속한 글자 중 최대 구간으로 정의한다. 아래 십자말풀이에서 DO와 ON은 단어의 예다.

회문 십자말풀이는 모든 단어가 회문인 십자말풀이다. Ri,j는 i번째 행, j번째 열의 글자를 나타내며 i와 j는 1부터 시작한다. 왼쪽 위 칸은 R1,1이다. 아래 회문 십자말풀이 예에서 R3,2의 B는 R3,1에서 시작하는 가로 단어와 R4,2에서 끝나는 세로 단어에 모두 속하며, 두 단어 모두 회문이다.

N행 M열의 회문 십자말풀이를 선물로 받았다. 십자말풀이를 다 풀고 단서를 버린 뒤 벽에 걸어 두려던 참에, 실수로 글자 일부를 지워 버렸다. 십자말풀이를 최대한 복원하고 싶지만 단서는 이제 없다. 십자말풀이가 회문이라는 사실만 가지고, 주어진 십자말풀이에서 빠진 글자를 최대한 많이 복원하자.

빠진 글자는 아래 그림에서 빈 흰 칸으로 나타낸다. 왼쪽 십자말풀이는 주어진 십자말풀이고, 오른쪽 십자말풀이는 글자를 최대한 복원한 결과다. 남은 칸은 복원할 정보가 충분하지 않아 채울 수 없다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 십자말풀이의 행 수와 열 수를 나타내는 두 정수 N과 M이 주어진다.

다음 N개 줄은 격자의 N개 행을 나타낸다. i번째 줄은 Ri,1, Ri,2, …, Ri,M을 나타내는 M개 문자로 이루어진다. 각 문자는 다음 중 하나다.

• 알파벳 대문자(A-Z)
• 빠진 글자를 나타내는 마침표(.)(예시 십자말풀이의 빈 흰 칸)
• 검은 칸을 나타내는 샵(#)

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 테스트 케이스 번호(1부터 시작)이고 y는 채운 빈 흰 칸의 수다. 그다음 N개 줄에 최종 격자를 출력한다. 빠진 글자(.)는 가능한 경우 알파벳 대문자(A-Z)로 바꾼다.

• 1 ≤ T ≤ 100.
• 주어진 입력 격자를 회문 십자말풀이가 되도록 채우는 방법이 적어도 하나 존재한다.
• 격자의 모든 문자는 {A-Z, #, .}에 속한다.

예제 2에서 빈칸 8개를 채울 수 있다. 빠진 글자를 다음과 같이 채울 수 있다.

• 1행 4열: 1행 1열의 글자에서 A임을 알 수 있다.
• 2행 4열=A, 1행 4열에서.
• 2행 6열=A, 2행 4열에서.
• 3행 6열=A, 2행 6열에서.
• 3행 2열=B, 3행 1열에서.
• 4행 2열=B, 3행 2열에서.
• 4행 3열=B, 4행 2열에서.
• 4행 4열=A, 4행 11열에서.