Crazy Rows (Small)

You are given an $N \times N$ matrix whose entries are 0 and 1. You can swap any two adjacent rows of the matrix.

Your goal is to have every 1 on the main diagonal or below it. That is, for each $X$ with $1 \le X \le N$, row $X$ must contain no 1 to the right of column $X$.

Report the minimum number of row swaps needed to reach the goal.

The first line contains the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains one integer $N$. Each of the next $N$ lines contains $N$ characters. Each character is either 0 or 1.

Limits

• $1 \le T \le 60$
• $1 \le N \le 8$

For each test case, print one line in the form

Case #X: K

where $X$ is the test case number starting from 1, and $K$ is the minimum number of row swaps needed to have every 1 on the main diagonal or below it.

Every test case has a solution.