Description

给定一个 $N \times N$ 的矩阵，矩阵中的元素仅为 $0$ 或 $1$。你可以交换矩阵中任意两行相邻的行。

你的目标是让矩阵中所有的 $1$ 都位于主对角线之下或在主对角线上。也就是说，对于每个 $X$，$1 \leq X \leq N$，第 $X$ 行中不能有 $1$ 出现在第 $X$ 列右侧的位置。

请你返回实现目标所需的最小行交换次数。

Input Format

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 组测试数据。

每组测试数据的第一行为一个整数 $N$。接下来的 $N$ 行，每行包含 $N$ 个字符，每个字符为 $0$ 或 $1$。

Output Format

对于每组测试数据，输出一行：

Case #X: K

其中 $X$ 是测试用例编号（从 $1$ 开始），$K$ 是实现目标所需的最小行交换次数。

保证每个测试用例都有解。

3
2
10
11
3
001
100
010
4
1110
1100
1100
1000

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

Hint

限制条件

• $1 \leq T \leq 60$

小数据集（6 分）

• $1 \leq N \leq 8$

大数据集（10 分）

• $1 \leq N \leq 40$

翻译由 ChatGPT-4.1 完成。