불판 위의 고기

Coders High 2014가 끝나고 출제진은 고깃집에 모여 고기를 시켰다. 고기를 굽는 중책은 명우가 맡았다. 문제 해결에 능한 명우는 불판 위의 고기를 이렇게 모델링했다.

불판은 $H \times W$개의 칸으로 이루어진 격자다. 고기 한 덩이는 격자의 여러 칸에 걸쳐 놓여 있고, 고기가 놓인 칸은 가득 채워진 것으로 본다.

시간이 지나 아래쪽 면이 적당히 구워졌으니 이제 고기를 뒤집을 때가 되었다.

한 덩이에 속한 고기는 뒤집을 때 통째로 같이 뒤집힌다. 첫 번째 그림이 원래 불판 위에 있던 상태다. 두 번째 그림은 고기를 좌우로 뒤집은 모습이다. 세 번째 그림은 뒤집기는 했지만 고기가 격자 칸에 제대로 맞물려 있지 않다. 명우는 이런 상태를 몹시 싫어하므로 이렇게 뒤집지 않는다. 네 번째 그림은 뒤집은 뒤 오른쪽으로 90도 돌린 모습인데, 이런 배치도 가능하다. 180도나 270도로 돌려도 된다.

명우는 모든 덩이가 뒤집힌 상태가 되도록 만들고 싶다. 완벽주의자라서 뒤집은 뒤에 고기가 겹치는 것도 몹시 싫어한다. 그러므로 어느 두 덩이도 겹쳐서는 안 되고, 모든 덩이는 불판 안에 들어와 있어야 한다.

조건을 만족하는 배치는 여러 가지가 나올 수 있다. 그중 무엇을 출력할지는 출력에서 정해 둔다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 격자의 크기를 나타내는 두 정수 $H$, $W$ ($1 \le H, W \le 11$)가 공백으로 구분되어 주어진다.

다음 $H$개의 줄에 불판의 현재 상태가 주어진다. 각 줄에는 $W$개의 문자가 공백 없이 주어지고, 각 문자는 알파벳 소문자이거나 .이다. 알파벳 소문자가 같은 칸끼리는 같은 덩이에 속한다. 같은 덩이라는 것은 그 덩이의 칸만 밟아 상하좌우로 움직여서 그 덩이의 다른 모든 칸에 갈 수 있다는 뜻이다.

각 테스트 케이스마다 고기를 뒤집은 뒤의 불판 상태를 $H$줄에 걸쳐 출력한다. 각 줄에는 $W$개의 문자가 있어야 한다.

출력할 배치는 불판 전체를 좌우로 뒤집은 것으로 정한다. 즉 입력으로 받은 각 줄의 문자를 역순으로 나열하고, 줄의 순서는 그대로 두어 출력한다. 불판 전체를 좌우로 뒤집으면 각 덩이는 자기 자신의 거울상이 되고, 어느 두 덩이도 겹치지 않으며, 불판을 벗어나는 덩이도 없다.

테스트 케이스의 출력 사이에는 빈 줄을 넣지 않는다.