恭喜你！你即将开始在著名的数字考古学家 Endiana Jones 手下实习。你的任务是评估 20 世纪 80 年代版本井字棋（Tic-Tac-Toe）游戏的存档结果。在那个年代，程序员的存储空间非常有限，因此他们尽可能紧凑地保存游戏状态。在本题中，状态存储在一个 32 位寄存器中。位 $0 - 8$ 存储了已落子的位置，位 $9 - 17$ 指示了该位置是 X 还是 O。对于位 $0 - 8$，置位（1）表示该位置已被占用；对于位 $9 - 17$，置位表示该位置由 X 占据。位 $18$ 指示了下一位玩家。（位从右向左编号，从最低有效位开始。）如果位 $18$ 被置位（为 1），则轮到 X 下棋。这些位的布局如图 M.1 所示：

图片所代表的游戏中，位 $0 - 8$ 均被置位，因为所有位置都已落子。位 $10, 11, 12$ 和 $15$ 会被置位，因为这些位置包含 X。位 $18$ 会被置位，因为接下来轮到 X 下棋。该状态的二进制表示为：1 001 001 110 111 111 111，八进制表示为 01116777。

该井字棋的实现非常简单，只有在所有位置都被填满后才会判定为平局（Cat’s game）。你的任务是根据给定的八进制整数来解释游戏状态。

井字棋简要回顾：两名玩家进行游戏。任何一方都可以先手。一名玩家的棋子为 X，另一名玩家为 O。每名玩家轮流在空位上放置自己的棋子。如果一名玩家在水平、垂直或对角线上连成三子，则该玩家获胜。如果没有获胜者且没有剩余空位，游戏停止，并判定为“平局”（Cat’s game）。

输入格式

输入的第一行包含一个十进制整数 $c$ ($1 \le c \le 10\,000$)，表示需要评估的状态数量。接下来的 $c$ 行，每行包含一个表示游戏状态的八进制数。所有数字都遵循以 0 开头的八进制书写惯例。所有游戏状态均为合法的，即在真实的井字棋游戏中可能出现的状态。

输出格式

对于每个游戏状态数字，打印一行表示游戏状态。四种可能的输出行如下：

X wins O wins Cat’s In progress

样例

输入格式 1

4
01116777
07037
01416777
050055

输出格式 1

O wins
X wins
Cat’s
In progress