헥스 판 상태 판정

헥스는 피트 하인과 존 내시가 각자 독립적으로 고안한 보드 게임이다. 이 문제는 헥스에서 아이디어를 가져왔지만, 헥스를 해 본 적이 없어도 풀 수 있다.

게임은 $N \times N$ 판에서 진행하고, 각 칸은 육각형이다. 빨강을 잡은 사람은 빨간 돌을, 파랑을 잡은 사람은 파란 돌을 쓴다. 판은 비어 있는 상태에서 시작하고, 두 사람은 번갈아 가며 자기 색 돌 하나를 판 위의 칸 하나에 놓는다. 색에 관계없이 이미 돌이 놓인 칸에는 놓을 수 없지만, 빈 칸이라면 어디에나 놓을 수 있다. 같은 색 돌 옆에 놓아야 한다는 제약은 없다. 누가 먼저 두는지는 두 사람 중에서 같은 확률로 무작위로 정한다.

판의 위쪽 변과 아래쪽 변은 빨강, 나머지 두 변은 파랑으로 표시한다. 자기 색으로 표시된 두 변을 자기 색 돌로 잇는 것이 목표이고, 먼저 이어 붙인 사람이 이긴다. 네 모서리 칸은 두 색 모두에 닿아 있는 것으로 본다. 승부가 나는 순간 게임은 곧바로 끝난다.

칸의 위치는 위에서 $i$번째 줄, 왼쪽에서 $j$번째 칸으로 나타낸다. 칸 $(i, j)$와 이웃한 칸은 $(i-1, j)$, $(i-1, j+1)$, $(i, j-1)$, $(i, j+1)$, $(i+1, j-1)$, $(i+1, j)$ 가운데 판 안에 있는 칸이다. 같은 색 돌이 이웃한 칸을 따라 죽 이어져 있으면 하나로 연결된 것이다. 빨강은 $i = 1$인 줄과 $i = N$인 줄을, 파랑은 $j = 1$인 열과 $j = N$인 열을 이어야 이긴다.

판의 상태가 주어지면 그 상태가 무엇인지 판정하는 프로그램을 작성하라. 답은 다음 넷 중 하나다.

• Impossible: 두 사람이 규칙을 지키며 두어서는 나올 수 없는 상태다.
• Red wins: 빨강이 이겼다.
• Blue wins: 파랑이 이겼다.
• Nobody wins: 아직 아무도 이기지 않았다. 헥스는 무승부로 끝나지 않으므로 승부는 아직 남아 있다.

나올 수 없는 상태라면 한쪽이 자기 색 두 변을 잇는 돌을 이미 놓았더라도 답은 Impossible 하나뿐이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 판 한 변의 길이 $N$이 주어진다. 다음 $N$개의 줄에는 길이가 $N$인 문자열이 한 줄씩 주어지며, 문자열은 B, R, .로만 이루어진다. B는 파란 돌이 놓인 칸, R은 빨간 돌이 놓인 칸, .은 빈 칸을 뜻한다.

제한

• $1 \le T \le 100$
• $1 \le N \le 10$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 판의 상태를 나타내는 Impossible, Blue wins, Red wins, Nobody wins 가운데 하나다. 대소문자를 구분하므로 impossible, blue wins, red wins, nobody wins는 오답으로 처리한다.