Inversions Organize

After the trouble with printing advertising for IO two years ago, the conference marketing team decided to use an interactive installation. It consists of a matrix of $2N$ rows and $2N$ columns of touchscreens. Each touchscreen can display either an uppercase I or an uppercase O. When one of the screens is touched, it switches to the letter it was not displaying right before the touch.

The installation you are looking at is disorganized. You want to change some letters so that the top $N$ rows show the same number of I's as the bottom $N$ rows, and the leftmost $N$ columns show the same total number of I's as the rightmost $N$ columns.

For example, in the left picture above, $N=2$. The top 2 rows show 3 I's in total, while the bottom 2 rows show 5. Both the leftmost 2 columns and the rightmost 2 columns show 4 I's. By touching the two highlighted screens, the state changes to the one in the right picture. It shows 4 I's in the top 2 columns and in the bottom 2 columns, and it keeps the left and right sides balanced.

Given the state of the installation, find the minimum number of letter changes needed to reach the goal.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing a single integer $N$, half the number of rows and columns of the matrix. Then, $2N$ lines follow. The $i$-th of these contains a string of $2N$ characters $C_{i,1}C_{i,2}\cdots C_{i,2N}$. $C_{i,j}$ is the letter currently displayed on the screen in the $i$-th row and $j$-th column of the matrix.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of touches required to make the installation display the same number of I's in its top and bottom halves, and the same number of I's in its left and right halves at the same time.

$1 \le T \le 100$.

For all $i, j$, $C_{i,j}$ is either an uppercase I or an uppercase O.

Sample Case #1 is the one explained in the statement. Not touching anything does not work, and a single touch would leave an odd number of I's in total, so the result cannot be balanced. The statement explains how to balance it with two touches (there are other ways).

In Sample Case #2, changing the top left corner to O leaves no I, so all halves have the same amount (0).

In Sample Case #3, the installation already meets the requirements, so no touch is needed.