X 제곱

올해 인기 있는 새 장난감은 "X 제곱"이다. 이 장난감은 N × N 크기의 정사각형 타일 격자로 이루어져 있으며, N은 홀수이다. 정확히 2 × N - 1개의 타일에 X가 적혀 있고 나머지는 비어 있다(빈 타일은 . 문자로 나타낸다). 게임의 각 이동에서 플레이어는 두 행을 골라 서로 바꾸거나, 두 열을 골라 서로 바꿀 수 있다. 게임의 목표는 모든 X 타일을 격자의 두 주대각선 위에 놓아 다음과 같이 큰 X 모양을 만드는 것이다(N = 5인 경우).

X...X
.X.X.
..X..
.X.X.
X...X

당신은 아직 목표 상태가 아닌 X 제곱 장난감을 가지고 게임을 시작하려 한다. 당신은 장난스러운 동생이 타일 몇 개를 옮겨 게임을 망가뜨렸을지도 모른다고 의심한다. 격자의 현재 상태가 주어졌을 때, 게임을 이길 수 있는지 판단할 수 있는가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 격자의 크기 N이 적힌 한 줄로 시작한다. 그다음 N개의 줄이 주어지며, 각 줄은 N개의 문자로 이루어져 있다. 이 줄들 중 i번째 줄의 j번째 문자는 i번째 행과 j번째 열에 있는 타일에 X가 적혀 있으면 X, 비어 있으면 .이다.

각 테스트 케이스에 대해 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 이길 수 있으면 POSSIBLE, 그렇지 않으면 IMPOSSIBLE이다.

• 1 ≤ T ≤ 100.
• N mod 2 = 1. (N은 홀수이다.)
• 격자에는 정확히 2 × N - 1개의 X 타일과 정확히 N2 - 2 × N + 1개의 . 타일이 있다.
• 격자는 문제 설명에서 설명한 목표 상태가 아니다.

예제 1에서는 다음과 같은 승리 전략이 있다.

1. 맨 위 행과 가운데 행을 바꾼다.
2. 맨 오른쪽 열과 가운데 열을 바꾼다.

 ..X    XX.    X.X
 XX. -> ..X -> .X.
 XX.    XX.    X.X

예제 2에서는 어떤 이동 순서로도 격자를 원하는 최종 상태로 만들 수 없다.