P13440 [GCJ 2009 #2] Crazy Rows

You are given an $N \times N$ matrix with $0$ and $1$ values. You can swap any two adjacent rows of the matrix. Your goal is to have all the $1$ values in the matrix below or on the main diagonal. That is, for each $X$ where $1 \leq X \leq N$, there must be no $1$ values in row $X$ that are to the right of column $X$. Return the minimum number of row swaps you need to achieve the goal.

The first line of input gives the number of cases, $T$. $T$ test cases follow. The first line of each test case has one integer, $N$. Each of the next $N$ lines contains $N$ characters. Each character is either $0$ or $1$.

For each test case, output 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 all the $1$ values in the matrix below or on the main diagonal. You are guaranteed that there is a solution for each test case.

**Limits** - $1 \leq T \leq 60$ **Small dataset(6 Pts)** - $1 \leq N \leq 8$ **Large dataset(10 Pts)** - $1 \leq N \leq 40$