Tic Tac Toe

Interview

Time limit1sMemory limit128 MB

Summary

Given a 3x3 Tic Tac Toe grid, decide whether some legal sequence of moves could produce exactly that position.

Level: Medium4 of 10
Topics: Implementation, Simulation, Brute force, Game theory
Solved: No attempts yet

Problem

Tic Tac Toe is a children's game played on a 3×3 grid. First, player X places an X on an empty cell. Then player O places an O on an empty cell. Play alternates between X and O until the grid is completely filled or one player's symbols occupy an entire line (horizontal, vertical, or diagonal).

We represent the initial empty grid with nine dots. Each time X or O plays, we fill in an X or an O at the chosen position. The example below shows every grid state from the start to the end of a game in which X wins.

...  X..  X.O  X.O  X.O  X.O  X.O  X.O
...  ...  ...  ...  .O.  .O.  OO.  OO.
...  ...  ...  ..X  ..X  X.X  X.X  XXX

Given a grid, determine whether it could be a snapshot of a valid Tic Tac Toe game. In other words, decide whether there is a sequence of moves that produces this grid at some point between the start and the end of the game.

Input

The first line contains $N$ , the number of test cases. The following $4N-1$ lines contain $N$ grids separated by empty lines. Each grid consists of three lines, and each line contains three characters, each of which is one of . (empty), X, or O.

Output

For each test case, print yes or no on its own line, indicating whether the grid could be part of a valid Tic Tac Toe game.

Examples1

Example 1
Input
```
2
X.O
OO.
XXX

O.X
XX.
OOO
```
Expected output
```
yes
no
```