Problem Description

Alice and Bob are really bored today, they want to play Tic-tac-toe.

The rules are basically the same as the general Tic-tac-toe chess. Two players, Alice and Bob, take turns to play on a $3 \times 3$ board. Alice goes first. The goal is to full fill their own chess pieces in a certain row, a certain column or a certain diagonal to form a continuous connection.

In our problem, the rules are somewhat different. Even if one player has reached a row (or a column or diagonal) connection, the game will continue until all the nine position are placed. Finally, we denote the number of connections of Alice minus the number of connections of Bob as the final score of the game. Alice wants to maximize the total score, while Bob wants to minimize it.

Due to some mysterious power, there have some chess pieces on the chessboard already. Alice and Bob want you to help calculate the final score starting with the given situation.

You can assume that Alice and Bob are both very smart.

Input

The first line of the input contains one integer $T$ $(1 \leq T \leq 40000)$, indicating the number of test cases.

For each test case, the first line is an integer $0$ or $1$ where $1$ means it is Alice's turn to play and $0$ means it is Bob's turn to play.

In the next three lines, each line contains 3 characters representing the situation of the chessboard:

$\qquad \cdot$ '.' represents a vacant position;

$\qquad \cdot$ 'O' represents Alice's chess piece has been placed;

$\qquad \cdot$ 'X' represents Bob's chess piece has been placed.

Output

Output $T$ lines.

For each test case, output one line containng one integer to represent the final score starting with the given situation.

2
0
.OO
X.O
OXO
1
XXX
XXX
XXX

2
-8