틱택토-토멕

틱택토-토멕은 4 x 4 크기의 정사각형 보드에서 하는 게임이다. 처음에 보드는 비어 있지만, 16개의 칸 중 하나에 단 하나의 'T' 기호가 있을 수도 있다. 두 플레이어 X와 O가 있다. X부터 시작하여 번갈아 수를 둔다. 각 수에서 플레이어는 빈칸 중 하나에 자신의 기호를 놓는다. Player X's 기호는 'X'이고, 플레이어 O의 기호는 'O'이다.

플레이어가 수를 둔 뒤, 그 플레이어의 기호 4개가 들어 있는 행, 열 또는 대각선이 있거나, 그 플레이어의 기호 3개와 'T' 기호가 들어 있는 행, 열 또는 대각선이 있으면 그 플레이어가 승리하고 게임이 끝난다. 그렇지 않으면 다른 플레이어가 수를 두며 게임을 계속한다. 모든 칸이 기호로 채워졌고 아무도 승리하지 못했다면 게임은 무승부로 끝난다. 다양한 승리 상황의 예시는 예제 입력을 참고한다.

현재 게임 상태를 나타내며 'X', 'O', 'T', '.' 문자를 포함하는 4 x 4 보드 설명이 주어진다('.'은 빈칸을 나타낸다). 진행 중인 틱택토-토멕 게임의 상태를 판별한다. 선택할 수 있는 상태는 다음과 같다.

• "X 승리" (게임이 끝났고 X가 승리함)

• "O 승리" (게임이 끝났고 O가 승리함)

• "Draw" (게임이 끝났고 무승부로 종료됨)

• "게임이 완료되지 않음" (게임이 아직 끝나지 않음)

빈칸이 있고 게임이 끝나지 않았다면, 게임의 결과가 불가피하더라도 "게임이 완료되지 않음"을 출력해야 한다.

제한

시간 제한: 테스트 세트마다 30초. 메모리 제한: 1GB. 주어지는 게임 보드는 위에서 설명한 틱택토-토멕 게임을 실제로 진행하여 도달할 수 있는 유효한 상태를 나타낸다.

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

1 ≤ T ≤ 10.

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

1 ≤ T ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 각각 4개의 문자를 포함하는 4개의 줄로 이루어지며, 각 문자는 'X', 'O', '.', 'T' 중 하나이다(따옴표는 명확성을 위해서만 사용되었다). 각 테스트 케이스 뒤에는 빈 줄이 하나 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에 제시된 상태 중 하나이다. 상태를 정확히 출력해야 한다. 예제 입력으로 코드를 실행하면 "Case #1: ", 숫자 "0"이 아닌 대문자 "O" 등을 포함하여 예제 출력과 정확히 같은 결과가 나와야 한다.

브라우저에서 예제 입력의 마지막 테스트 케이스 뒤에 있는 빈 줄이 표시되지 않을 수도 있지만, 실제 입력 파일에는 해당 빈 줄이 있다.