Problem AF
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 Xs and Os 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.

4
XX..O....
X...OX...
OOOX.X.X.
OOOXXX...

191 194
232 200
0 1
-1 -1