Let Me Count the Ways

input file: `count.in`

An important feature of smart game playing programs is the ability to evaluate the relative goodness of different game scenarios.

Tic-tac-toe is played on a three by three board by two players, who are traditionally called 'X' and 'O'. For the sake of this game, 'X' will move first. Play alternates between the players. Each player places exactly one of their markers on one of the blank spaces of the board. The game is won when one player has placed three of their markers in a row horizontally, vertically, or diagonally. No moves are made once the game is won. Below are three snapshots of boards:

      Board 1         Board 2         Board 3

     O | X | O       O | X | O       O | X | O
    ---+---+---     ---+---+---     ---+---+---
       | X |           | X | O         | X |
    ---+---+---     ---+---+---     ---+---+---
     X |   |         X |   |         X | O |

In Board 1, it is O's turn to move and Boards 2 and 3 show two of the possible moves O can make.

In deciding what move to next make, some players will see how many different final configurations are reachable from the current board and of those final configurations, how many would give the win to each of the players. From Board 2 above, there are 4 more reachable configurations, with 2 of them giving the win to X and 1 giving the win to O:

     No wins           O win           X win           X win

     O | X | O       O | X | O       O | X | O       O | X | O
    ---+---+---     ---+---+---     ---+---+---     ---+---+---
     X | O | O       X | X | O         | X | O       O | X | O
    ---+---+---     ---+---+---     ---+---+---     ---+---+---
     X | O | X       X |   | O       X | X |         X | X | X

Note that there is no assumption of intelligence in the players! While a human player might always work to win the game or block the opponent if possible, this problem is just asking for possible configurations, not smart ones.

From Board 3 above, there are 3 more reachable configurations, with 1 of them giving the win to X and none giving the win to O:

      No win           X win           No win

     O | X | O       O | X | O       O | X | O
    ---+---+---     ---+---+---     ---+---+---
     X | X | O       X | X | X       O | X | X
    ---+---+---     ---+---+---     ---+---+---
     X | O | X       X | O | O       X | O | O

Your program must take an initial tic-tac-toe board and compute how many legal possible final configurations are reachable from the starting board, and in how many of those X wins, and in how many of those O wins. Your final configurations must have at least one move past the initial board in order to be counted.

Input

The input to this program will be a positive integer n which tells how many initial boards to examine. There will then be n boards with three lines each, three characters on each line. An 'X' represents a square with an X, an 'O' represents a square with an O, and an underscore ('_') represents an empty square.

You may assume all boards have valid configurations that could occur in a game.

Output

For each input board, print the number of the board, the number of final configurations (where numbering starts at 1), the number of those the X player wins, and the number the O player wins. Have one blank line after each line of output. Follow the format in the Sample Output below.

Sample Input

2
OXO
_XO
X__
OXO
_X_
XO_

Output corresponding to the Sample Input