알파벳 케이크 (스몰)

아이들 파티에 낼 케이크가 $R$행 $C$열의 격자 모양이다. 보조 요리사가 아이마다 이름의 첫 글자를 케이크의 한 칸에 크림으로 적어 두었다. 한 칸에 적힌 글자는 많아야 하나이고, 첫 글자가 같은 아이는 없으므로 같은 글자가 두 번 나오지 않는다.

아이는 저마다 자기 글자가 들어 있고 다른 아이의 글자는 들어 있지 않은 직사각형 조각 하나를 원한다. 조각의 변은 격자선과 나란해야 한다. 빈 칸을 하나도 남기지 않고 모두 어느 한 아이에게 배정해서 이 조건을 맞춰라. 배정이 가능한 입력만 주어진다. 케이크를 똑같이 나눌 필요는 없고, 어떤 아이는 $1 \times 1$ 조각만 받기도 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $R$과 $C$가 공백으로 구분되어 주어진다. 그다음 줄부터 $C$개의 문자로 이루어진 줄이 $R$개 주어지고, 케이크를 나타낸다. 각 문자는 대문자 알파벳이거나 ?이다. 대문자 알파벳은 그 칸에 이미 적힌 글자를 뜻하고, ?는 빈 칸을 뜻한다.

제한:

• $1 \le T \le 100$
• $1 \le R \le 12$
• $1 \le C \le 12$
• $R \times C \le 12$
• 입력 격자에 글자가 적어도 하나 있다.
• 같은 글자가 두 칸 이상에 나오지 않는다.
• 각 테스트 케이스마다 조건을 만족하는 배정이 적어도 하나 존재한다.

각 테스트 케이스마다 먼저 Case #x:만 적힌 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호다. 그다음 $C$개의 문자로 이루어진 줄을 $R$개 출력한다. 출력 격자는 입력 격자와 같되 ?가 모두 대문자 알파벳으로 바뀌어 있어야 하고, 그 글자는 그 칸이 어느 아이의 조각에 속하는지를 뜻한다. 입력에 없던 글자를 새로 적을 수 없다. 또 각 글자마다 그 글자가 적힌 칸 전체가 격자선과 나란한 직사각형 하나를 이루어야 한다.

조건을 만족하는 격자가 여럿이면 그중 하나만 정답으로 인정한다. 격자의 각 줄을 왼쪽에서 오른쪽으로 읽고 줄을 위에서 아래 순서로 이어 붙여 길이 $R \times C$의 문자열을 만들 때, 이 문자열이 사전순으로 가장 작은 격자를 출력하라.