헥스 (라지)

헥스는 Piet Hein과 John Nash가 각각 독립적으로 고안한 보드 게임이다. 이 문제는 헥스에서 아이디어를 가져왔지만, 헥스를 해 본 적이 없어도 풀 수 있다.

게임은 각 칸이 육각형인 $N \times N$ 판에서 진행한다. 빨강 돌을 쓰는 빨강과 파랑 돌을 쓰는 파랑, 두 사람이 겨룬다. 판은 비어 있는 상태에서 시작하고, 두 사람은 번갈아 가며 빈 칸 하나에 자기 색 돌을 놓는다. 어느 색 돌도 놓여 있지 않은 칸이면 어디에나 놓을 수 있고, 같은 색 돌 옆에 놓아야 한다는 제약은 없다. 누가 먼저 두는지는 두 사람 중에서 같은 확률로 무작위로 정한다.

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

행은 위에서부터 $1$번부터 $N$번까지, 열은 왼쪽에서부터 $1$번부터 $N$번까지 번호를 매긴다. 아래쪽 행일수록 육각형이 바로 윗 행보다 오른쪽으로 반 칸씩 밀려 있어서, 칸 $(r, c)$와 변을 맞대는 칸은 $(r, c-1)$, $(r, c+1)$, $(r-1, c)$, $(r-1, c+1)$, $(r+1, c-1)$, $(r+1, c)$ 여섯 개다. 이 중 판 밖으로 나가는 것은 제외한다. 빨강은 $1$행과 $N$행을, 파랑은 $1$열과 $N$열을 자기 돌로 잇는다.

판의 상태가 주어지면 다음 넷 중 어느 것인지 판정하시오.

• Impossible: 두 사람이 규칙을 지키면서 그 상태에 이르는 것이 불가능한 경우.
• Red wins: 빨강이 이긴 경우.
• Blue wins: 파랑이 이긴 경우.
• Nobody wins: 아직 아무도 이기지 않은 경우. 헥스는 승자 없이 끝나지 않는다.

불가능한 상태라면 빨강이나 파랑이 자기 색 두 변을 잇는 길을 이미 만들어 놓았더라도 답은 Impossible뿐이다.

아래는 $6 \times 6$ 판에서 파랑이 이긴 예다. 파랑이 먼저 두어 $1$번 칸에 파랑 돌을 놓았고, 이어서 빨강이 $2$번 칸, 파랑이 $3$번 칸에 놓는 식으로 진행했다. $11$번째 돌을 놓는 순간 파랑이 이긴다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 판 한 변의 길이 $N$이 주어지고, 다음 $N$개의 줄에는 각각 $N$개의 문자로 이루어진 판이 주어진다. 문자는 'B', 'R', '.' 세 가지뿐이다. 'B'는 파랑 돌이 놓인 칸, 'R'은 빨강 돌이 놓인 칸, '.'은 빈 칸이다.

제한

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

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 판의 상태로 Impossible, Blue wins, Red wins, Nobody wins 중 하나다. 대소문자를 구분하므로 impossible, blue wins, red wins, nobody wins처럼 쓰면 틀린 답이 된다.