Hex

이 문제는 Piet Hein와 John Nash가 서로 독립적으로 설계한 Hex라는 보드게임에서 영감을 받았다. 비슷한 발상을 사용하지만, Hex를 해 본 적이 있다고 가정하지는 않는다.

이 게임은 각 칸이 육각형인 NxN 보드에서 진행한다. 빨간 돌을 사용하는 빨강 측과 파란 돌을 사용하는 파랑 측, 두 명의 플레이어가 있다. 보드는 빈 상태로 시작하며, 두 플레이어는 번갈아 가며 전체 게임 보드 안의 한 칸에 자신의 색깔 돌을 놓는다. 각 플레이어는 어떤 색깔의 다른 돌도 놓여 있지 않은 아무 칸에나 자신의 돌을 놓을 수 있다. 돌을 같은 색깔의 다른 돌 옆에 놓아야 한다는 조건은 없다. 먼저 시작할 플레이어는 무작위로 결정된다(두 플레이어가 선택될 확률은 같다).

보드의 위쪽 변과 아래쪽 변은 빨간색으로 표시되고, 나머지 두 변은 파란색으로 표시된다. 게임의 목표는 한 플레이어의 색깔로 표시된 보드의 두 변을 그 플레이어의 돌로 연결하는 연결된 경로를 만드는 것이다. 이를 먼저 달성한 플레이어가 승리한다. 네 모서리는 두 색깔 모두와 연결된 것으로 간주한다는 점에 유의한다.

한 플레이어가 승리하면 게임은 즉시 끝난다.

게임 상태가 주어질 때, 이 게임을 처음 접하는 사람이 게임 보드의 상태를 판정할 수 있도록 도와주자. 다음 중 하나를 답한다.

• "Impossible": 두 플레이어가 규칙을 따르면서 해당 게임 상태에 도달하는 것이 불가능한 경우.

• "Red wins": 빨간 돌을 두는 플레이어가 승리한 경우.

• "Blue wins": 파란 돌을 두는 플레이어가 승리한 경우.

• "Nobody wins": 아직 아무도 게임에서 승리하지 않은 경우. Hex 게임은 승자 없이 끝날 수 없다는 점에 유의한다!

불가능한 상태에서는 빨강이나 파랑이 자신의 색깔로 표시된 보드의 서로 마주 보는 두 변을 잇는 연결된 돌의 경로를 만들었더라도, 유일하게 올바른 답은 "Impossible"임에 유의한다.

다음은 파랑이 승리한 6x6 게임 보드의 게임 예제이다. 파랑이 먼저 시작하여 1로 표시된 칸에 파란 돌을 놓았다. 그런 다음 빨강이 2 칸에 놓고, 이어서 파랑이 3 칸에 놓는 식으로 진행한다. 11번째 돌을 놓은 뒤 파랑이 승리한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

1 ≤ T ≤ 100.

테스트 세트 1 - 공개

1 ≤ N ≤ 10.

테스트 세트 2 - 비공개

1 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 보드 한 변의 크기 N으로 시작한다. 이어서 'B', 'R', '.' 문자로만 이루어진 N행 N열의 보드가 주어진다. 'B'는 파란 돌이 놓인 칸을, 'R'은 빨간 돌이 놓인 칸을, '.'은 빈 칸을 나타낸다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 게임 보드의 상태이다. y는 "Impossible", "Blue wins", "Red wins", "Nobody wins" 중 하나일 수 있다(따옴표 제외). 채점기는 대소문자를 구분하므로 "impossible", "blue wins", "red wins", "nobody wins"는 오답으로 판정된다는 점에 유의한다.