Description

你刚刚建成了一家全新的工厂。你的工厂有 $\mathbf{N}$ 台不同的机器，并且每台机器都需要恰好一名工人来操作，才能保证工厂正常运转。

你也雇佣了 $\mathbf{N}$ 名工人来操作这些机器。由于你招聘时很匆忙，并没有核查他们是否真的会操作你的机器。现在你终于询问了每个人，得知对于每个 $i$ 和 $j$，第 $i$ 个工人是否会操作第 $j$ 台机器的信息。

在一个典型的工作日，工人们会以随机顺序到达工厂，每天的顺序可能不同。每当一名工人到达时，他会查看所有自己会操作且尚未被占用的机器，并从中随机选择一台，全天进行操作。如果他会操作的所有机器都已被占用，那么当天他就不会工作。你的目标是，无论工人到达的顺序和他们在有多种选择时的选择如何，都能保证每天所有机器都有人操作。

举个例子，假设有两名工人 $\mathrm{A}$ 和 $\mathrm{B}$，以及两台机器 1 和 2。假设 $\mathrm{A}$ 会操作 1 号和 2 号机器，$\mathrm{B}$ 只会操作 1 号机器。如果 $\mathrm{B}$ 先到，他会选 1 号机器，$\mathrm{A}$ 到时只能选 2 号，这样工厂能正常运转。但如果 $\mathrm{A}$ 先到，她可能选择 1 号机器，这时 $\mathrm{B}$ 就没法工作，2 号机器没人操作，导致工厂当天无法正常运转！

再比如，假设仍有两名工人 $\mathrm{A}$ 和 $\mathrm{B}$，两台机器 1 和 2，且 $\mathrm{A}$ 只会操作 1 号机器，$\mathrm{B}$ 什么都不会操作。无论工人到达顺序如何，工厂都无法正常运转。

在工厂开业前，为了保证工厂永远都能正常运转，你可以培训工人学会操作新机器。给一名工人培训一台机器的费用为 1 美元。每次培训只涉及一名工人和一台机器，但你可以给任意多名工人、任意多台机器进行培训，同一名工人可以接受多次培训。如果某名工人已经会操作某台机器，你不能让他忘掉。

例如，上述两个例子都可以通过教 $\mathrm{B}$ 操作 2 号机器来解决。这样无论到达顺序和选择如何，每台机器都能保证有人操作。

请问，为了保证每天工厂都能正常运转，你最少需要花多少钱培训工人？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例。每组数据的第一行为一个整数 $\mathbf{N}$，表示工人（和机器）数量。之后有 $\mathbf{N}$ 行，每行是一个长度为 $\mathbf{N}$ 的字符串，第 $i$ 行第 $j$ 个字符为 1 表示第 $i$ 个工人会操作第 $j$ 台机器，为 0 表示不会。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 为保证所有 $\mathbf{N}$ 台机器始终有人操作所需的最小培训费用。

5
2
11
10
2
10
00
3
000
000
000
1
1
3
000
110
000

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

Hint

样例解释

样例第 1 组和第 2 组即为题面中的示例。

在第 3 组中，没有人会操作任何机器！一种最优方案是教 $\mathrm{A}$ 操作 1 号机器，$\mathrm{B}$ 操作 2 号机器，$\mathrm{C}$ 操作 3 号机器。

第 4 组无需任何操作。只有一名工人，他已经会操作唯一的那台机器。

第 5 组中，$\mathrm{B}$ 已会操作 1 号和 2 号机器。一种最优方案是教 $\mathrm{A}$ 操作 3 号机器，并让 $\mathrm{A}$ 成为唯一能操作该机器的人。但此时必须考虑 $\mathrm{B}$ 可能会选择 1 号或 2 号机器，因此 $\mathrm{C}$ 还需要学会操作剩下的那一台。所以 $\mathrm{C}$ 必须被教会操作 1 号和 2 号机器。

限制条件

• $1 \leqslant \mathbf{T} \leqslant 100$。

小数据集（6 分，测试集 1 - 可见）

• $1 \leqslant \mathbf{N} \leqslant 4$。

大数据集（25 分，测试集 2 - 隐藏）

• $1 \leqslant \mathbf{N} \leqslant 25$。

翻译由 GPT4.1 完成。