IO 설치물 정리

2년 전 IO 광고물 인쇄에 문제가 있었던 뒤, 대회 마케팅 팀은 인터랙티브 설치물을 쓰기로 했다. 이 설치물은 $2N$개의 행과 $2N$개의 열로 이루어진 터치스크린 행렬이다. 각 터치스크린은 대문자 I 또는 대문자 O를 표시한다. 화면을 터치하면 터치 직전에 표시하던 글자가 아닌 다른 글자로 바뀐다.

지금 보고 있는 설치물은 정리가 되어 있지 않다. 일부 글자를 바꿔서 위쪽 $N$개 행의 I 개수가 아래쪽 $N$개 행의 I 개수와 같게 하고, 동시에 왼쪽 $N$개 열의 I 총개수가 오른쪽 $N$개 열의 I 총개수와 같게 만들려고 한다.

위 왼쪽 그림에서 $N=2$이다. 위쪽 2개 행에는 I가 총 3개 있고, 아래쪽 2개 행에는 5개 있다. 왼쪽 2개 열과 오른쪽 2개 열에는 각각 I가 4개씩 있다. 강조된 두 화면을 터치하면 오른쪽 그림의 상태가 된다. 이 상태에서는 위쪽 2개 열과 아래쪽 2개 열에 I가 각각 4개씩 있고, 좌우 균형도 유지된다.

설치물의 상태가 주어졌을 때, 목표를 이루는 데 필요한 글자 변경 횟수의 최솟값을 구하라.

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 위쪽 절반과 아래쪽 절반의 I 개수가 같고 동시에 왼쪽 절반과 오른쪽 절반의 I 개수도 같아지도록 하는 데 필요한 터치 횟수의 최솟값이다.

$1 \le T \le 100$.

모든 $i, j$에 대해 $C_{i,j}$는 대문자 I 또는 대문자 O이다.

샘플 케이스 1은 문제 설명에서 든 경우이다. 아무것도 터치하지 않으면 조건을 만족하지 못하고, 한 번만 터치하면 I의 총개수가 홀수가 되어 균형을 맞출 수 없다. 설명처럼 터치 두 번으로 균형을 맞출 수 있다(다른 방법도 있다).

샘플 케이스 2에서는 왼쪽 위 모서리를 O로 바꾸면 I가 남지 않으므로, 모든 절반이 0개로 같다.

샘플 케이스 3에서는 설치물이 이미 조건을 만족하므로 터치가 필요 없다.