Coin Game

Sangwoo invented a game played with coins. Nine coins lie in a 3 by 3 grid. A coin showing heads is written H, and a coin showing tails is written T.

H T T
H T T
T H H

The goal is to make all nine coins show the same face, either all H or all T. Flipping a single coin is not allowed. One move flips the three coins of a row, the three coins of a column, or the three coins on a diagonal. There are two diagonals here, the one running from the top left to the bottom right and the one running from the top right to the bottom left. Flipping three coins this way counts as one move.

Sangwoo wants the number of moves to be as small as possible. The grid above takes two moves, and one move is not enough.

H T T   T T T   T T T
H T T → T T T → T T T
T H H   H H H   T T T

Some grids cannot be made uniform at all. Here is one of them.

T H H
H H H
H H H

Write a program that helps Sangwoo by computing the minimum number of moves for each grid.

The first line contains the number of test cases $T$ ($1 \le T \le 10$). Each test case consists of three lines, and each line gives the state of three coins as H or T. Values on the same line are separated by one space.

For each test case, print on its own line the minimum number of moves that makes all nine coins show the same face. Print -1 when it is impossible.