#1167 동전 게임

42  1 s   128 MB  

Description

상우는 재미있는 게임을 생각해냈다. 동전 9 개를 아래 그림과 같이 3 행 3 열로 놓는다. H 는 앞면, T 는 뒷면을 의미한다.

 

H T T

H T T

T H H

 

게임의 목적은 이 동전의 모양을 모두 같은 면(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

 

상우를 도울 수 있는 프로그램을 작성하시오.

 

 

Input

입력은 표준입력(standard input)을 통해 받아들인다.
입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다.
각 테스트 케이스는 세 줄로 이루어지며 한 줄에 세 개의 동전모양이 주어지는데 각각의 동전 표시 사이에는 하나의 공백으로 구분이 된다.

 

 

Output

출력은 표준출력(standard output)을 통하여 출력한다.
각 테스트 케이스에 대해서, 모두 같은 면이 보이도록 만들기 위한 최소의 연산횟수를 출력한다.
만약 그것이 불가능하다면 -1 을 출력하시오.

 

 

 

Sample Input

Sample Output

3
H T T
H T T
T H H
T H H
H H H
H H H
H H H
H T H
H H H
2
-1
4