Description

Supervin 是一位著名的编舞家。今天是他编舞生涯的第 $N$ 周年。为此，他计划在一个 $N \times N$ 的正方形舞台上编排一场舞蹈。每个格子上恰好站着一名舞者。

每位舞者都将穿着一套服装；每套服装只有一种颜色，并且材质为羊毛或棉布。Supervin 在为舞者设计服装时有 $N$ 种颜色可选，编号为 $1$ 到 $N$。

每位舞者都希望自己与众不同。如果同一行或同一列中有两位或更多舞者穿着颜色和材质都相同的服装，他们就不会感到特别。

Supervin 希望所有舞者都能感到特别。因此，他准备更改一些舞者服装的颜色和/或材质，使得没有任何两位舞者在同一行或同一列中穿着完全相同的服装（即颜色和材质都相同）。请问，最少需要更改多少位舞者的服装，才能满足上述要求？（注意，更改服装的颜色和材质都只算作一次更改。）

Input Format

输入的第一行是测试用例的数量 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为一个整数 $N$，表示舞台的边长。接下来的 $N$ 行，每行包含 $N$ 个非零整数 $A_{i,j}$。第 $i$ 行第 $j$ 列的值表示第 $i$ 行第 $j$ 列舞者的服装。数值的绝对值表示颜色，符号表示材质（负号表示羊毛，正号表示棉布）。

Output Format

对于每组测试数据，输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示最少需要更改服装的舞者人数。

4
2
1 2
2 1
2
1 1
2 1
2
1 2
1 2
2
2 2
-2 2

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

Hint

样例解释

在样例 1 中，不需要更改任何服装，因为没有舞者在同一行或同一列中穿着完全相同的服装。

在样例 2 中，一种最优方案是将 $\mathbf A$ 更改为如下（加粗表示更改过的值）：

  1 -2
  2 1

也存在其他最优方案。注意，更改服装的颜色和材质都只算作一次更改。

在样例 3 中，一种最优方案是将 $\mathbf A$ 更改为如下（加粗表示更改过的值）：

  1 2
  2 1

也存在其他最优方案。

在样例 4 中，一种最优方案是将 $\mathbf A$ 更改为如下（加粗表示更改过的值）：

  2 -2
  -2 2

也存在其他最优方案。

数据范围

• $1 \leq T \leq 100$。
• 对所有 $i, j$，$-N \leq A_{i,j} \leq N$。
• 对所有 $i, j$，$A_{i,j} \neq 0$。

测试点 1（7 分，公开）

• $2 \leq N \leq 4$。

测试点 2（17 分，隐藏）

• $2 \leq N \leq 100$。

由 ChatGPT 4.1 翻译