Crazy Rows (Large)

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

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

Find 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 0 or 1.

Limits

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

For each test case, print one line in this format.

Case #X: K

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

Every test case is guaranteed to have a solution.