# Problem M

Tic-Tac State

Congratulations! You are starting your internship for the famous digital archaeologist, Endiana Jones. You have been assigned to evaluate the results of saved games of a 1980’s version of Tic-Tac-Toe. In those days, programmers had very little storage, so they saved game state as compactly as possible. In this case, the state was in a 32-bit register. Bits $0-8$ stored the positions that had been played and bits $9-17$ indicated an X or O. A set bit ($1$ bit) indicated a played position for bits $0-8$ or that X played for bits $9-17$. Bit 18 indicated the next player to play. (Bits are numbered from right to left, starting at the least-significant bit.) If bit $18$ is set (is $1$), it is X’s turn to play next. Visually the bits were laid out as shown in Figure 1:

The game represented by the picture would have bits
$0-8$ set because all
positions have been played. Bits $10$, $11$, $12$, and $15$ would be set because those
positions contain an X. Bit $18$ would be set because it would be
X’s turn next. The state would be represented in binary as:
`1 001 001 110 111 111 111` or in octal
as $01116777$.

The Tic-Tac-Toe implementation was very simple, and a cat’s
game (draw or tie) was not called until all positions had been
played. Your task is to interpret the state of the game given
an **octal** integer.

**Quick review of Tic-Tac-Toe:** Two
players play the game. Either player may go first. One player’s
mark is X and the other’s is O. Each player takes turns placing
their mark in one of the empty squares. If a player gets three
marks in a horizontal, vertical, or diagonal row, that player
wins. If there is no winner and there are no empty spaces left,
the game stops, and the game is declared “Cat’s” game.

## Input

The first line of input consists of a single decimal integer
$c$ ($1 \leq c \leq 10\, 000$), the number
of states to evaluate. Each of the following $c$ lines will have a single **octal** number representing the state of a game.
All numbers will follow the convention of writing octal numbers
with a leading $0$. All
game states will be legal, that is, achievable in a real game
of Tic-Tac-Toe.

## Output

For each game state number print a single line indicating the state of the game. The four possible output lines are:

X wins O wins Cat's In progress

Sample Input 1 | Sample Output 1 |
---|---|

4 01116777 07037 01416777 050055 |
O wins X wins Cat's In progress |