每年，你的教授都会在门上贴一张空白的报名表，用于一场著名的科学研究会议。如果学生想在会议上发表演讲，他们会选择一个表上尚未出现的双词主题，并将其写在表上。一旦截止日期过去，教授会让一名研究生将这些主题随机排序，以避免对早签到的学生产生偏见。然后，她会将这些主题呈现给你进行审核。

由于会议上的零食非常棒，一些学生试图通过伪造来混入会议。他们选择表上已有主题的第一个词，以及表上已有主题的第二个词，并将它们组合起来（第一个词在前，第二个词在后）以创建一个新的“主题”（前提是该主题尚未出现在表上）。由于你的教授思想开明，这种策略有时确实有效！

伪造者完全没有原创性，他们无法自己想出任何新的第一个词或第二个词；他们必须使用表上已有的词。此外，他们不会试图将一个现有的第一个词用作他们自己的第二个词（除非该词也已经作为第二个词存在于表上），反之亦然。

你有一份包含所有 $N$ 个已提交主题的列表，顺序是任意的；你不知道它们实际写在表上的顺序。其中最多有多少个主题可能是伪造的？

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含一行整数 $N$，随后是 $N$ 行，每一行代表一个不同的主题，包含两个由大写英文字母组成的字符串：即该主题的两个词，按顺序排列。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个整数：可能被伪造的主题的最大数量。

数据范围

每个测试集的时限：20 秒。 内存限制：1 GB。 $1 \le T \le 100$。 $1 \le$ 每个单词的长度 $\le 20$。 每个用例中没有重复的主题。

小型数据集（测试集 1 - 可见） $1 \le N \le 16$。

大型数据集（测试集 2 - 隐藏） $1 \le N \le 1000$。

样例

输入 1

3
3
HYDROCARBON COMBUSTION
QUAIL BEHAVIOR
QUAIL COMBUSTION
3
CODE JAM
SPACE JAM
PEARL JAM
2
INTERGALACTIC PLANETARY
PLANETARY INTERGALACTIC

输出 1

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

说明

在样例 1 中，一种可能性是主题按以下顺序添加到表中： QUAIL BEHAVIOR（真实） HYDROCARBON COMBUSTION（真实） QUAIL COMBUSTION（伪造）

不存在任何场景使得超过一个主题是伪造的。

在样例 2 中，所有主题都必须是真实的。无论它们以什么顺序写下，在任何时候都不可能使用现有单词来创建一个不在列表上的新主题。

在样例 3 中，两个主题都不能是伪造的。例如，如果 INTERGALACTIC PLANETARY 是第一个也是唯一一个写在表上的主题，伪造者只能使用 INTERGALACTIC 作为新主题的第一个词，并且只能使用 PLANETARY 作为新主题的第二个词……但伪造者唯一能组成的主题将是 INTERGALACTIC PLANETARY，由于它已经在表上，这是不允许的。因此，PLANETARY INTERGALACTIC 也必须是一个真实的主题。