키파-틱택토

틱택토는 두 명이 번갈아가며 O와 X를 3×3 판에 써서 같은 글자를 가로, 세로, 혹은 대각선 상에 놓이도록 하는 놀이입니다.[1] 틱택토는 상대적으로 단순한 전략 놀이로, 몇 번 해 보면 양쪽이 최선을 다하는 경우 비긴다는 사실을 알 수 있습니다.

키파는 틱택토가 너무 단순한 놀이라고 생각해서, 틱택토를 더욱 확장한 키파-틱택토를 만들었습니다. 키파-틱택토는 유비트의 판 모양과 비슷한 4×4 판에서 진행하며, X부터 시작하여 번갈아 가며 판을 한 칸씩 채웁니다. 각 칸을 아래와 같이 부르겠습니다.

키파는 틱택토의 승리 조건도 너무 단순하다고 생각했고, 비기는 경우가 있는 것도 마음에 안 들어서, 승리 조건 역시 바꾸었습니다. 일단 판을 모두 채워 X가 여덟 개, O가 여덟 개 있는 상황에서, 아래와 같은 승리 조건에 따라 승자를 결정합니다.

플레이어는 놀이 중 차례에 상관없이 승리를 선언할 수 있습니다. 현재 열여섯 칸이 모두 채워지지 않았지만, 이 상태에서 게임이 규칙에 따라 어떻게 진행되더라도 최종적으로 승리 조건에 따라 이기는 사람이 한 사람으로 정해져 있을 수 있습니다. 이 경우 그 사람은 승리 선언 조건을 만족합니다. 플레이어가 승리 선언 조건을 만족한 상태에서 승리를 선언하면 놀이에서 곧바로 이깁니다. 열여섯 칸이 모두 채워진 경우 승리를 선언할 수 없음에 유의하세요.

이 놀이를 완벽하게 익힌 키파와 아바나가 키파-틱택토를 합니다. 키파는 아바나에게 선을 양보했습니다. 놀이가 이미 어느 정도 진행되었고, 여기서부터 양쪽이 최선을 다하는 경우 키파-틱택토가 어떻게 진행되는지를 계산하는 프로그램을 작성하세요.

첫째 줄에 테스트 케이스의 수 T가 주어집니다. T는 1 이상 300 000 이하입니다.

각 테스트 케이스는 총 네 줄로 이루어져 있습니다. 각 줄에는 정확히 네 개의 문자로 이루어진 문자열이 주어집니다. 각 문자는 O, X 또는 . 중 하나이며, 테스트 케이스의 i행에 주어진 문자열의 j번째 문자가 O나 X인 경우 i행 j열에 그 문자가 그려져 있음을, .인 경우 아무 것도 그려져 있지 않음을 의미합니다.

모든 테스트 케이스는 빈 판에서 올바르게 놀이를 진행한 상태입니다. 즉, 열여섯 개의 문자 중 X의 개수에서 O의 개수를 뺀 값을 D라 하면, D가 0인 경우는 현재 X의 차례, D가 1인 경우는 현재 O의 차례이며, 이외의 경우는 입력으로 주어지지 않습니다.

각각의 테스트 케이스에 대해, KIPA WINS, HAVANA WINS, KIPA DECLARES A WIN, HAVANA DECLARES A WIN 중 하나를 한 줄에 출력합니다.