GOV05 - Tic-tac-toe

Everyone knows about the famous game of Tic-Tac-Toe. I am very fond of this game.

Actually, I consider it as the world's best game. But my friend Harshit thinks that I am no good at this game. When I tried to convince him, but he simply laughed at me and made fun of me. After hours of argument, he finally gave me a challenge to solve. I am busy at the moment so I need your help. Please solve the challenge for me. I need to prove myself before Harshit, so don't let me down. The challenge is as follows:

You will be simply given the picture of a Tic-Tac-Toe Game. By just looking at that picture, you have to tell its game-status. The list of possible game-status is:

  • O - 'O' has won.
  • X - 'X' has won.
  • C - The match is still under progress.
  • I - The given scenario is impossible to occur, if all the rules are followed.
  • D - The match has been drawn.

Note: Do not predict the result. Just tell the status of immediate scenario.

Input

First line of input contains a number N. Then there is a blank line. Then N test cases follows.

For each test case, you will be given the picture of game. The pictures will be of three line. (Each line having 3 characters without any spaces)

  • '.' represents blank box.
  • 'O' represents box marked with 'O'. (Letter 'O' not zero.)
  • 'X' represents box marked with 'X'.

There is a blank line after every test case.

Output

Answer to every test case is a single character indicating the game-status of given scenario.

You have to print a single string containing answers of all the test cases.

Example

Input:
7

OX.
OX.
OX.

OXX
.OX
..O

X.O
.X.
..X

X.O
.X.
O.X

XOO
OOX
XXO

XO.
OOX
XXO

OXX
OXX
OOO


Output:
IOIXDCO

Added by:Govind Lahoti
Date:2013-04-11
Time limit:1s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:self

hide comments
2014-11-05 23:09:55 Francky
There's "only" 19683 cases, that makes a full data set under 200kB. Possible to be entirely checked in reasonable time, isn't it?
@Mitch : you should set a new task in challenge or shorten with all the cases. Or if you want to play, ask kokosek to add it by its own. What about that?
2014-11-05 20:28:31 Mitch Schwartz
(1) In the standard rules of Tic Tac Toe, X always goes first, but for this problem either X or O can go first.
(2) Test data is weak. I got AC with code that doesn't handle a certain class of cases. (My second submission.)

This is a nice problem. I may suggest it to be added to SHORTEN with a few modifications. (My first submission isn't very golfed -- I probably won't put more effort into this version of the problem.)

@Francky: My plan is to prepare everything and then ask Piotr publish it on SHORTEN. It could be ok for challenge section too, but I lean against that idea because (1) it's somewhat easy to solve, and (2) I like to promote variety in challenge section, and golf problems are somewhat over-represented lately.

A straightforward approach in Python can handle all possible cases in well under a second on Cube, so that would probably work. (And it would be closer to 250 kB of data, if we include whitespace.)

Last edit: 2014-11-06 04:07:05
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.