X 제곱

올해의 인기 신상 장난감은 "X 제곱"이라고 한다. 이 장난감은 타일로 이루어진 N × N 정사각형 격자로 구성되며, N은 홀수이다. 타일 중 정확히 2 × N - 1개에는 X가 표시되어 있고, 나머지는 비어 있다(빈 타일은 . 문자로 나타낸다). 게임에서 한 번 움직일 때마다 플레이어는 타일의 두 행을 골라 서로 바꾸거나, 타일의 두 열을 골라 서로 바꿀 수 있다. 게임의 목표는 모든 X 타일을 격자의 두 주대각선 위에 놓아 더 큰 X 모양을 만드는 것이며, N = 5인 다음 예제와 같다.

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

이제 아직 목표 상태가 아닌 X 제곱 장난감을 가지고 놀려고 한다. 짓궂은 동생이 게임을 망가뜨리는 방식으로 타일 일부를 옮겼을지도 모른다고 의심하고 있다. 현재 격자의 배치가 주어질 때, 게임에서 이길 수 있는지 판별할 수 있는가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. N mod 2 = 1. (N은 홀수이다.) 격자에는 정확히 2 × N - 1개의 X 타일과 정확히 $N^{2}$ - 2 × N + 1개의 . 타일이 있다. 격자는 문제 설명에 정의된 목표 상태가 이미 되어 있지는 않다.

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ N ≤ 5.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ N ≤ 55.

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

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 이길 수 있으면 POSSIBLE, 그렇지 않으면 IMPOSSIBLE이다.

예제 케이스 #1에서 이기는 전략 중 하나는 다음과 같다.

• 맨 위 행과 가운데 행을 서로 바꾼다.

• 맨 오른쪽 열과 가운데 열을 서로 바꾼다.

예제 케이스 #2에서는 어떤 순서로 움직여도 격자를 원하는 최종 배치로 바꿀 수 없다.