你刚刚建立了一座全新的工厂。你的工厂有 $N$ 台不同的机器，每台机器都需要恰好一名工人来操作，工厂才能正常运转。

你还雇佣了 $N$ 名工人来操作这些机器。由于雇佣时比较匆忙，你没有检查他们是否真的知道如何操作你的机器。现在你终于询问了他们，因此你掌握了每名工人 $i$ 是否知道如何操作每台机器 $j$ 的信息。

在典型的工作日中，工人们会以随机的顺序到达工厂，每天的顺序可能不同。当每名工人到达时，他们会找到所有他们知道如何操作且尚未被分配操作员的机器。他们会随机选择其中一台，并在整个工作日内操作它。如果他们知道如何操作的所有机器都已经有了操作员，他们当天就不会工作。你的目标是确保每天所有机器都有人操作，无论工人们以什么顺序到达，也无论他们选择哪台机器。

例如，假设有两名工人 A 和 B，以及两台机器 1 和 2。假设 A 知道如何操作 1 和 2，而 B 知道如何操作 1 但不知道如何操作 2。如果工人 B 先到达，他会选择机器 1，然后当工人 A 到达时，她必须选择 2，工厂将正常运转。然而，如果工人 A 先到达，可能会发生她选择操作 1 的情况，那么当工人 B 到达时，他将无事可做，导致机器 2 没有操作员，从而使你的工厂浪费一整天！

再举一个例子，假设有两名工人 A 和 B，以及两台机器 1 和 2，且 A 知道如何操作 1 但不知道如何操作 2，而 B 什么都不会。那么，无论工人们以什么顺序到达，工厂都无法正常运转。

在工厂开业之前，为了保证工厂能持续正常运转，你可以教工人们如何操作机器。教一名工人学习操作一台机器需要花费一美元。每节课只涉及一名工人和一台机器，但你可以教任意数量的课程给任意数量的工人，同一名工人也可以接受多节课程。如果工人已经知道如何操作某台机器，你不能让他们忘记。

例如，上述两个例子都可以通过教工人 B 操作机器 2 来解决。在这种情况下，无论工人们以什么顺序到达，也无论他们在有多种选择时选择操作哪台机器，每台机器都能保证每天有操作员。

你需要花费的最少美元数是多少，才能确保工厂每天都能正常运转？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，即工人（和机器）的数量。接下来是 $N$ 行，每行包含一个长度为 $N$ 的字符串。如果第 $i$ 行的第 $j$ 个字符为 $1$，则表示第 $i$ 名工人知道如何操作第 $j$ 台机器，否则为 $0$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个非负整数：为了确保所有 $N$ 台机器始终有操作员，你需要花费的最少美元数。

数据范围

时间限制：每个测试集 20 秒。 内存限制：1 GB。 $1 \le T \le 100$。

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

$1 \le N \le 4$。

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

$1 \le N \le 25$。

样例

样例输入 1

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

样例输出 1

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

说明

样例 #1 和 #2 是题目描述中提到的例子。

在样例 #3 中，没有人知道如何操作任何机器！一种最优策略是教工人 A 操作机器 1，教工人 B 操作机器 2，教工人 C 操作机器 3。

在样例 #4 中，不需要采取任何行动。只有一名工人，且该工人已经知道如何操作那台机器。

在样例 #5 中，工人 B 已经知道如何操作机器 1 和 2。一种最优策略是教工人 A 操作机器 3，并使 A 成为唯一能操作该机器的工人。但现在我们必须考虑到 B 到达时可能会操作机器 1 或 2，因此 C 需要能够操作 B 未选择的那台机器。所以必须教 C 同时操作 1 和 2。