알파벳 케이크 (라지)

아이들의 파티 음식을 맡아서 $R$행 $C$열 격자 모양 케이크를 낸다. 조수가 아이마다 이름의 첫 글자를 아이싱으로 케이크의 한 칸에 적어 두었다. 한 칸에는 글자가 많아야 하나 있고, 첫 글자가 같은 아이는 없으므로 같은 글자가 두 번 나오지도 않는다.

아이들은 각자 자기 글자가 들어 있고 다른 아이의 글자는 들어 있지 않은 조각 하나를 원한다. 조각은 격자에 맞춰 자른 직사각형이어야 한다. 빈 칸을 모두 어느 한 아이에게 나누어 주어 이 조건을 맞춰라. 답은 항상 존재한다. 케이크를 똑같이 나눌 필요는 없고, 어떤 아이는 1×1 조각만 받기도 한다. 세상이 공평하지 않다는 것을 배우는 인생 수업이라고 해 두자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $R$와 $C$가 주어진다. 그 다음 줄부터 $C$개의 문자로 이루어진 줄이 $R$개 주어지며, 케이크를 나타낸다. 각 문자는 영어 대문자이거나 ?다. 대문자는 조수가 그 칸에 이미 적어 둔 글자를 뜻하고, ?는 빈 칸을 뜻한다.

제한

• $1 \le T \le 100$
• $1 \le R \le 25$
• $1 \le C \le 25$
• 각 테스트 케이스의 격자에는 글자가 적어도 하나 있다.
• 한 격자에서 같은 글자가 두 칸 이상에 나타나지 않는다.
• 각 테스트 케이스마다 답이 적어도 하나 존재한다.

각 테스트 케이스마다 Case #x:를 한 줄에 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 그 다음 $C$개의 문자로 이루어진 줄을 $R$개 출력한다. 출력 격자는 입력에 글자가 있던 칸의 글자를 그대로 두고 모든 ?를 영어 대문자 하나로 바꾼 것이어야 한다. 바꾼 글자는 그 칸이 그 글자를 받은 아이의 조각에 들어간다는 뜻이다. 입력에 없던 글자는 쓸 수 없다. 각 글자마다 그 글자가 적힌 칸 전체가 격자에 맞춘 직사각형 하나를 이루어야 한다.

조건을 만족하는 격자가 여러 개일 수 있으므로, 다음 규칙으로 만든 격자 하나만 정답으로 인정한다.

1. 글자가 하나 이상 있는 행에서는, 그 행의 첫 글자보다 왼쪽에 있는 빈 칸을 모두 그 첫 글자로 채우고, 나머지 빈 칸은 같은 행에서 자기 왼쪽에 가장 가까이 있는 글자로 채운다.
2. 글자가 하나도 없는 행은 위쪽에서 가장 가까우면서 글자가 있는 행을 1번 규칙으로 완성한 결과를 그대로 복사한다. 위쪽에 글자가 있는 행이 없으면 아래쪽에서 가장 가까우면서 글자가 있는 행을 복사한다.