1161. Tic-Tac-Toe ( I )

Problem code: TOE1

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.

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
```

 Added by: Camilo Andrés Varela León Date: 2006-12-14 Time limit: 1s Source limit: 50000B Memory limit: 256MB Cluster: Pyramid (Intel Pentium III 733 MHz) Languages: All except: ERL JS NODEJS PERL 6 Resource: Waterloo local 2002.09.21

2013-05-14 14:27:16 aman jain
friends be careful:
in this x can win twice over diagonals.
not considering will lead to WA.

Last edit: 2013-05-14 15:30:41
2013-03-27 12:34:41 killerz
@Tigran Galstyan
In case 1
XXO
OOX
OXX
chance num of X is 1 3 5 7 9
here O had won thus no extra X ,ie, game finishes at chance num 8 ; thus invalid !!!
2013-03-03 19:35:48 Tigran Galstyan
@kamalesh why 1st case is "NO"??
2013-02-20 16:36:17 Eslam Zanaty
@Viktor Fonic
this case prints YES its a valid case
2013-02-07 10:44:34 Viktor Fonic
This one caused me a lot of trouble:
XOX
OXX
OOX
no
2013-01-20 11:51:20 Apurva Kumar
Is X always playing first?If not then please explain 2nd test case.

Last edit: 2013-01-20 12:16:01
2013-01-15 00:34:50 Haijun Deng
One more test case:
XX.
X..
OOO
yes
2012-12-31 04:57:11 kamalesh
INPUT:
3
XXO
OOX
OXX

XXX
OO.
..O

XXX
OOO
...

OUTPUT:
no
no
no
which caused me 2 WA's

Last edit: 2012-12-31 04:57:59
2012-12-24 18:18:09 SuMiT BaNsAl
i have checked for more than 50 test cases. still getting wrong ans.
my submission id: 8337937
2012-12-19 14:07:54 Jayaprakash S
:-)