题目描述

Pari 是一位强大的仙女，正在为保护精灵王国免受邪恶女巫的侵害而战斗。女巫们一天比一天强大，因此 Pari 必须使用魔法棒来施展保护咒语。她可以通过将魔法棒排列成一个面积非零的凸多边形来实现这一点。

然而，Pari 不一定能使用她想要的任何魔法棒！精灵王国中所有可用的魔法棒都紧密地组合在一起，形成一个图，其中边是魔法棒，节点是一根或多根魔法棒的端点。（魔法棒除了在端点处，永远不会相互接触，它们具有魔力！）每当 Pari 取走一根魔法棒用于咒语时，所有与该魔法棒相邻（即共享一个节点）的魔法棒都会永远消失，并且以后无法使用。

Pari 想知道有多少种不同的魔法棒子集可以从图中取出并用于形成一个面积非零的凸多边形。所有魔法棒都被视为不同的，即使长度相同也是如此。两个魔法棒子集不同当且仅当至少存在一根魔法棒只出现在其中一个子集中。如上所述，一个子集是有效的当且仅当存在一种方式，将该子集中的所有魔法棒从图中取出，且没有一根魔法棒因相邻而提前消失。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示魔法棒构成的图中节点的个数。然后有 $N$ 行，每行包含 $N$ 个整数 $L_{i, j}$。第 $i$ 行第 $j$ 个值表示端点在第 $i$ 个节点和第 $j$ 个节点的魔法棒的长度，如果不存在这样的魔法棒则为 $0$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述有效子集的个数。

4
6
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
0 0 0 0 1 0
6
0 2 0 0 0 0
2 0 0 0 0 0
0 0 0 3 0 0
0 0 3 0 0 0
0 0 0 0 0 4
0 0 0 0 4 0
6
0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 2 0 0
0 0 2 0 0 0
0 0 0 0 0 4
0 0 0 0 4 0
6
0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0

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

1
8
0 5 0 0 0 0 0 0
5 0 0 0 0 0 0 0
0 0 0 5 0 0 0 0
0 0 5 0 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 5
0 0 0 0 0 0 5 0

Case #1: 5

提示

在样例 #1 中，包装图包含 $5$ 条长度相等的边；用它们连接的节点表示，这些边为 1-2、2-3、3-4、4-5 和 5-6。要形成一个封闭多边形，至少需要 $3$ 条边，但唯一能取出 $3$ 条边的方式是选择边 1-2、3-4 和 5-6。

在样例 #2 中，图包含 $3$ 条边，1-2、3-4 和 5-6。注意图可以不连通。我们可以用长度为 $2$、$3$ 和 $4$ 的边组成一个三角形。

在样例 #3 中，图包含 $3$ 条边，1-2、3-4 和 5-6。但我们无法用长度分别为 $1$、$2$ 和 $4$ 的边组成一个封闭多边形。

在样例 #4 中，我们无法取出超过 $1$ 条边。

限制条件

$1 \le T \le 100$。

对于所有 $i, j$，$0 \le L_{i, j} \le 1000$。

对于所有 $i$，$L_{i, i} = 0$。

对于所有 $i, j$，$L_{i, j} = L_{j, i}$。

小数据集

$N = 6$。

大数据集

$6 \le N \le 15$。

翻译由 DeepSeek V4 Pro 完成