# Problem C

Tic Tac Toe Counting

Tic Tac Toe is a simple children’s game. It is played on a
$3 \times 3$ grid. The
first player places an `X` in any of
the $9$ cells. The next
player places an `O` in any of the
remaining 8 cells. The players continue to alternate placing
`X`s and `O`s
in unoccupied cells until either a player gets three of their
symbols in a row, or the grid is full. If either player gets
three in a row, in any of the three rows, three columns or two
diagonals, that player wins and the game ends.

Fred and Sam are playing a game of Tic Tac Toe. In the
middle of the game, Fred wonders: “How many games from this
point in the game onward are winners for `X`? How many for `O`?”
Two games are different if they have different sequences of
moves, even if they result in the grid looking the same at any
point.

Given a list of grids, determine first if they can be
reached in a game of Tic Tac Toe, and if they can, how many
games from that point on result in wins for `X`, and how many for `O`.

## Input

The first line of input contains a single integer $t$ ($1 \le t \le 10^5$), which is the number of test case grids.

Each of the next $t$
lines contains a single string $s$ ($|s|=9$) which consists of only the
characters `‘.’`, `‘X’` and/or `‘O’`. These
are the test case grids. The first three characters represent
the first row, the second three are the second row, and the
last three are the last row, with `‘.’`
representing an empty cell. For example, the string `XX..O....` represents this grid:

## Output

For each test case, output two space-separated integers. If
the grid is not reachable in a game of Tic Tac Toe, output
`-1 -1`. If the grid is reachable,
output the number of games from that point on (including that
grid) that are wins for `X`, followed
by wins for `O`.

Sample Input 1 | Sample Output 1 |
---|---|

4 XX..O.... X...OX... OOOX.X.X. OOOXXX... |
191 194 232 200 0 1 -1 -1 |