틱택토 상태

축하한다! 유명한 디지털 고고학자 Endiana Jones의 인턴으로 일하게 되었다. 당신은 1980년대 버전 틱택토의 저장된 게임 결과를 분석하는 일을 맡았다. 그 시절 프로그래머들은 저장 공간이 매우 부족했기 때문에 게임 상태를 최대한 압축해서 저장했다. 이 경우 상태는 32비트 레지스터에 저장되었다. 비트 $0$ − $8$은 이미 놓인 위치를, 비트 $9$ − $17$은 X 또는 O를 나타낸다. 비트 $0$ − $8$에서 세트된 비트(1 비트)는 놓인 위치를, 비트 $9$ − $17$에서 세트된 비트는 X가 놓았음을 나타낸다. 비트 $18$은 다음 차례의 플레이어를 나타낸다. (비트는 최하위 비트부터 오른쪽에서 왼쪽으로 번호를 매긴다.) 비트 $18$이 세트되어 있으면(1이면) 다음 차례는 X이다. 시각적으로 비트는 그림 M.1과 같이 배치되었다:

그림 M.1: 게임 상태의 비트

그림에 나타난 게임은 모든 위치가 놓였기 때문에 비트 $0$ − $8$이 세트되어 있을 것이다. 비트 $10$, $11$, $12$, $15$는 해당 위치에 X가 있으므로 세트되어 있을 것이다. 비트 $18$은 다음 차례가 X이므로 세트되어 있을 것이다. 이 상태는 이진수로 1 001 001 110 111 111 111, 8진수로 $01116777$로 표현된다.

틱택토 구현은 매우 단순했고, 무승부(묘사 게임)는 모든 위치가 놓일 때까지 선언되지 않았다. 당신의 임무는 8진수 정수가 주어졌을 때 게임 상태를 해석하는 것이다.

틱택토 복습: 두 플레이어가 게임을 한다. 어느 플레이어든 먼저 둘 수 있다. 한 플레이어의 표시는 X이고 다른 플레이어의 표시는 O이다. 각 플레이어는 번갈아 가며 빈 칸 중 하나에 자신의 표시를 놓는다. 한 플레이어가 가로, 세로, 대각선 줄에 세 개의 표시를 놓으면 그 플레이어가 이긴다. 승자가 없고 빈 칸이 남아 있지 않으면 게임이 끝나고 "Cat's" 게임으로 선언된다.

입력의 첫 줄에는 평가할 상태의 수 $c$ ($1 ≤ c ≤ 10\,000$)가 십진 정수로 주어진다. 다음 $c$개의 줄에는 각각 게임 상태를 나타내는 8진수 하나가 주어진다. 모든 수는 8진수를 나타낼 때 앞에 $0$을 붙이는 관례를 따른다. 모든 게임 상태는 합법적이며, 즉 실제 틱택토 게임에서 나올 수 있는 상태이다.

각 게임 상태 번호에 대해 게임 상태를 나타내는 줄을 하나씩 출력한다. 가능한 출력 줄은 다음 네 가지이다:

O wins
X wins
Cat's
In progress