TOE1 - Tic-Tac-Toe ( I )


Tic Tac Toe is a child's game played on a 3 by 3 grid. One player, X, starts by placing an X at an unoccupied grid position. Then the other player, O, places an O at an unoccupied grid position. Play alternates between X and O until the grid is filled or one player's symbols occupy an entire line (vertical, horizontal, or diagonal) in the grid.

We will denote the initial empty Tic Tac Toe grid with nine dots. Whenever X or O plays we fill in an X or an O in the appropriate position. The example below illustrates each grid configuration from the beginning to the end of a game in which X wins.

subir imagenes

Your job is to read a grid and to determine whether or not it could possibly be part of a valid Tic Tac Toe game. That is, is there a series of plays that can yield this grid somewhere between the start and end of the game?

Input

The first line of input contains N, the number of test cases. 4N-1 lines follow, specifying N grid configurations separated by empty lines.

Output

For each case print "yes" or "no" on a line by itself, indicating whether or not the configuration could be part of a Tic Tac Toe game.

Example

Input:
2
X.O
OO.
XXX

O.X
XX.
OOO

Output:
yes
no

hide comments
:D: 2011-10-08 07:26:26

Yes it is. Just look for a sequence of moves, it is simple for such a small field.

AKSHAY TANEJA: 2011-10-07 08:49:43

is this a valid one..?

0X0
XXX
0X0

suteerth: 2011-12-29 20:48:36

oops ! :)

:D: 2010-04-02 15:42:41

The "X" player always starts, not "O".

suteerth: 2010-04-02 15:37:22

How come this is not a valid state ?
O.X
XX.
OOO

It could have come from steps like these -

O.. | O.. | O.. | O.. | O.. | O.X | O.X
... | .X. | .X. | XX. | XX. | XX. | XX.
... | ... | O.. | O.. | O.O | O.O | OOO

Why should we assume that the players will be playing optimally, a brainless player might as well put a X somewhere else instead of putting it between 2 O's, and lose the game, or it might even be a mistake.

Last edit: 2010-04-02 15:43:19
Ponsamuel Mervin: 2009-08-31 08:54:57

X O X
O . O
X O X

This is a valid one. X has to be placed next. so the answer is

X O X
O X O
X O X

Thus X can win twice :)

Last edit: 2009-08-31 08:55:33
Daniel Ferizovic: 2009-08-09 11:05:08

X O X
O X O
X O X

or

X X X
O O X
O O X

Last edit: 2009-08-09 11:06:41
ahmed samir: 2009-08-09 10:45:33

how can x win twice somebody give me example

Ali Rabiee: 2009-07-30 16:25:43

u're right Dan. it can play somehow that X wins twice.

Ali Rabiee: 2009-07-30 09:22:13

are the tests valid themselves?
I have considered all cases but I get WA.

Last edit: 2009-07-30 09:58:10

Added by:Camilo Andrés Varela León
Date:2006-12-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Waterloo local 2002.09.21