동전 게임

상우가 동전으로 하는 게임을 하나 만들었다. 동전 9개를 3행 3열로 놓고, 앞면이 보이는 동전은 H, 뒷면이 보이는 동전은 T로 적는다.

H T T
H T T
T H H

게임의 목표는 동전 9개가 모두 같은 면을 보이게, 즉 전부 H이거나 전부 T가 되게 만드는 것이다. 동전 하나만 뒤집을 수는 없다. 한 번에 한 행의 동전 세 개, 한 열의 동전 세 개, 또는 대각선 하나에 놓인 동전 세 개를 뒤집어야 한다. 여기서 대각선은 왼쪽 위에서 오른쪽 아래로 가는 것과 오른쪽 위에서 왼쪽 아래로 가는 것, 두 개다. 이렇게 동전 세 개를 한꺼번에 뒤집는 것을 연산 한 번으로 센다.

상우는 연산 횟수를 최소로 줄이고 싶다. 위 배치는 연산 두 번이면 되고, 한 번으로는 안 된다.

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

배치에 따라서는 모두 같은 면으로 만드는 것이 아예 불가능하다. 다음이 그런 배치다.

T H H
H H H
H H H

상우를 도와 각 배치의 최소 연산 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지고, 한 줄에 동전 세 개의 상태가 H 또는 T로 주어진다. 같은 줄의 값 사이에는 공백이 하나씩 있다.

테스트 케이스마다 동전 9개가 모두 같은 면을 보이게 만드는 최소 연산 횟수를 한 줄에 하나씩 출력한다. 불가능하면 -1을 출력한다.