# CodeChef: May Long Challenge | Tic Tac Toe | TCTCTOE | Solution

View on Codechef

Tic-tac-toe is a game played between two players on a 3×33×3 grid. In a turn, a player chooses an empty cell and places their symbol on the cell. The players take alternating turns, where the player with the first turn uses the symbol XX and the other player uses the symbol OO. The game continues until there is a row, column, or diagonal containing three of the same symbol (XX or OO), and the player with that token is declared the winner. Otherwise if every cell of the grid contains a symbol and nobody won, then the game ends and it is considered a draw.

You are given a tic-tac-toe board AA after a certain number of moves, consisting of symbols OO, XX, and underscore(__). Underscore signifies an empty cell.

Print

• 11: if the position is reachable, and the game has drawn or one of the players won.
• 22: if the position is reachable, and the game will continue for at least one more move.
• 33: if the position is not reachable.

### Input

• The first line contains an integer TT, the number of test cases. Then the test cases follow.
• Each test case contains 33 lines of input where each line contains a string describing the state of the game in ithith row.

### Output

For each test case, output in a single line 11, 22 or 33 as described in the problem.

### Constraints

• 1≤T≤391≤T≤39
• Aij∈{X,O,_}Aij∈{X,O,_}

Subtask #1 (100 points): Original Constraints

### Sample Input

``````3
XOX
XXO
O_O
XXX
OOO
___
XOX
OX_
XO_
``````

### Sample Output

``````2
3
1
``````

### Explanation

Test Case 11: The board is reachable, and although no player can win from this position, still the game continues.

Test Case 22: There can’t be multiple winners in the game.

Test Case 33: The first player is clearly a winner with one of the diagonals.

``Solution will be updated here soon. Keep tracking``