在进行外星探索时，你发现了外星诗歌的证据！你的语言学家团队确定，外星语言中的每个单词都在单词中的某一个位置（字母）上有重音；从重音字母开始的单词部分被称为重音后缀。如果两个单词的重音后缀相同，则称这两个单词押韵。例如，单词 PROL 和 TARPOL，如果它们的重音字母都是 O 或 L，则它们押韵；但如果重音字母分别是 R，或者 PROL 的重音字母是 R 而 TARPOL 的重音字母是 P，又或者 PROL 的重音字母是 O 而 TARPOL 的重音字母是 L，则它们不押韵。

你收集了一个包含 $N$ 个单词的列表，这些单词可能是外星诗歌的一部分。不幸的是，你不知道每个单词的重音字母在哪里。你认为你可以丢弃零个或多个单词，为剩余的单词分配重音字母，然后将这些单词两两配对，使得每个单词只与配对中的另一个单词押韵，而不与其它配对中的任何单词押韵。

你想要知道以这种方式可以配对的单词的最大数量。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行是一个整数 $N$。随后有 $N$ 行，每行包含一个由大写英文字母组成的字符串 $W_i$，代表一个不同的单词。注意，同一个单词在不同的测试用例中可能有不同的重音分配。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足上述条件的最大单词子集的大小。

数据范围

$1 \le T \le 100$。 $1 \le$ $W_i$ 的长度 $\le 50$，对于所有 $i$。 $W_i$ 由大写英文字母组成，对于所有 $i$。 $W_i \neq W_j$，对于所有 $i \neq j$。（单词在同一个测试用例中不会重复。）

子任务 1（可见） $2 \le N \le 6$。

子任务 2（隐藏） $2 \le N \le 1000$。

样例

样例输入 1

4
2
TARPOL
PROL
3
TARPOR
PROL
TARPRO
6
CODEJAM
JAM
HAM
NALAM
HUM
NOLOM
4
PI
HI
WI
FI

样例输出 1

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

说明

在样例 1 中，如上所述，通过适当的重音分配，这两个单词可以押韵，因此最大的子集是整个输入。

在样例 2 中，无论我们如何分配重音，没有任何两个单词可以押韵，因为任意两个后缀至少在最后一个字母上不同。因此，最大的子集是空集，大小为 0。

在样例 3 中，如果我们对 CODEJAM 和 JAM 在 J 处加重音，对 HAM 和 NALAM 在它们最后的 A 处加重音，对 HUM 和 NOLOM 在 M 处加重音，我们就可以使用整组单词。

在样例 4 中，任意两个单词都可以通过将重音字母设为 I 来押韵。因此，如果我们向子集中添加两对，来自不同配对的单词也会押韵。因此，我们只能通过选择任意 2 个输入单词来形成大小为 2 的子集。