금고

금고의 앞면은 $N \times N$ 격자이고, 칸마다 손잡이가 하나씩 달려 있다. 손잡이는 수평(-) 아니면 수직(|), 이 두 상태뿐이며 돌리면 다른 쪽 상태로 바뀐다.

손잡이 번호는 아래 왼쪽 그림처럼 맨 윗줄 왼쪽에서 오른쪽으로, 그다음 줄로 내려가면서 1번부터 $N^2$번까지 붙어 있다. 처음에는 오른쪽 그림처럼 모든 손잡이가 수평이다. 금고문은 모든 손잡이가 수평일 때만 열린다.

문이 열린 처음 상태에서 다음과 같이 문을 잠근다. 손잡이 하나를 골라 돌리면 그 손잡이의 방향이 바뀐다. 수평이면 수직이 되고, 수직이면 수평이 된다. 여기서 중요한 점은 고른 손잡이와 같은 행, 같은 열에 있는 손잡이의 방향도 함께 바뀐다는 것이다.

예를 들어 처음 상태에서 6번 손잡이를 돌리면 아래 왼쪽 그림처럼 되고, 그 상태에서 다시 11번 손잡이를 돌리면 오른쪽 그림처럼 된다.

잠긴 금고의 상태가 주어진다. 모든 손잡이를 수평으로 되돌려 금고문을 열려면 손잡이를 최소 몇 번 돌려야 하는지 구하라.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 각 테스트 케이스의 첫 줄에는 금고의 크기 $N$이 주어지며, $N$은 2 이상 20 이하의 짝수이다. 이어지는 $N$개의 줄에 금고의 상태가 한 줄에 $N$개씩 주어진다. 각 문자는 H 또는 V이고 공백 하나로 구분한다. H는 수평인 손잡이, V는 수직인 손잡이를 뜻한다.

출력은 표준 출력으로 한다. 테스트 케이스마다 금고를 열기 위해 손잡이를 돌려야 하는 최소 횟수를 한 줄에 하나씩 출력한다.