반전 정리

두 해 전 IO의 광고 인쇄와 관련해 문제가 발생한 후, 대회의 마케팅 팀은 대화형 설치물을 사용하기로 했다. 이 설치물은 터치스크린이 $2\mathbf{N}$행과 $2\mathbf{N}$열로 배치된 행렬로 이루어져 있다. 각 터치스크린에는 대문자 I 또는 대문자 O를 표시할 수 있다. 화면 하나를 터치하면, 터치가 발생하기 직전에 표시하지 않던 글자로 표시가 바뀐다.

여러분은 이러한 설치물 중 하나를 보고 있으며, 이것이 정리되어 있지 않다고 생각한다. 위쪽 $\mathbf{N}$개 행에 표시된 글자 I의 수가 아래쪽 $\mathbf{N}$개 행에 표시된 수와 같고, 동시에 가장 왼쪽의 $\mathbf{N}$개 열에 표시된 글자 I의 총수가 가장 오른쪽의 $\mathbf{N}$개 열에 표시된 수와 같아지도록 일부 글자를 바꾸려고 한다.

예를 들어, 위의 왼쪽 그림에서 $\mathbf{N}=2$. 위쪽 $2$개 행에는 글자 I가 총 $3$개 표시되어 있는 반면, 아래쪽 $2$개 행에는 $5$개가 표시되어 있다. 한편, 가장 왼쪽의 $2$개 열과 가장 오른쪽의 $2$개 열에는 모두 글자 I가 $4$개 표시되어 있다. 강조 표시된 두 화면을 터치하면 상태를 오른쪽 그림과 같이 바꿀 수 있다. 이 그림에서는 위쪽 $2$개 열과 아래쪽 $2$개 열에 글자 I가 각각 $4$개 표시되며, 왼쪽과 오른쪽 사이의 균형도 유지된다.

설치물의 상태가 주어질 때, 정리 목표를 달성하는 데 필요한 최소 글자 변경 횟수를 구할 수 있는가?

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i, j$에 대해, $\mathbf{C_{i,j}}$는 대문자 I 또는 대문자 O이다.

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{N} \le 2$.

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{N} \le 100$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 행렬의 행 수와 열 수의 절반인 하나의 정수 $\mathbf{N}$를 포함하는 줄로 시작한다. 그다음 $2\mathbf{N}$개의 줄이 주어진다. 이 중 $i$번째 줄에는 $2\mathbf{N}$개의 문자로 이루어진 문자열 $\mathbf{C_{i,1}}\mathbf{C_{i,2}}\cdots\mathbf{C_{i,2N}}$가 주어진다. $\mathbf{C_{i,j}}$는 행렬의 $i$번째 행과 $j$번째 열에 있는 화면에 현재 표시된 글자이다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 설치물의 위쪽 절반과 아래쪽 절반에 표시된 글자 I의 수가 같고 동시에 왼쪽 절반과 오른쪽 절반에 표시된 글자 I의 수가 같도록 만드는 데 필요한 최소 터치 횟수이다.

예제 케이스 #1는 문제 설명에서 설명한 경우이다. 아무것도 터치하지 않으면 조건을 만족하지 않으며, 한 번만 터치하면 글자 I의 총수가 홀수가 되므로 균형을 이룰 수 없다. 두 번 터치하여 균형을 이룰 수 있는 방법은 문제 설명에 나와 있다(다른 방법도 있다).

예제 케이스 #2에서는 왼쪽 위 모서리를 O로 바꾸면 글자 I가 하나도 남지 않으므로, 모든 절반에 같은 수($0$)가 있게 된다.

예제 케이스 #3에서는 설치물이 이미 요구 사항에 맞게 정리되어 있으므로 터치할 필요가 없다.