Crazy Rows (Small)

Time limit5sMemory limit512 MB

Summary

Given an N by N binary matrix, reorder the rows using adjacent swaps so each row's rightmost 1 is at or left of its position, minimizing swaps.

Level: Medium5 of 10
Topics: Greedy, Sorting, Array, Brute force
Solved: No attempts yet

Problem

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.

Input

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$

Output

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.

Examples3

Example 1

Input

Expected output

Case #1: 0
Case #2: 2
Case #3: 4

Example 2
Input
```
2
1
0
1
1
```
Expected output
```
Case #1: 0
Case #2: 0
```

Example 3

Input

Expected output

Case #1: 1
Case #2: 0
Case #3: 0