Description

在一次外星探索中，你发现了外星诗歌的证据！你的语言学家团队确定，外星语言中的每个单词都有且只有一个字母带有重音；从重音字母开始到单词结尾的部分称为“重音后缀”。如果两个单词的重音后缀相同，则称这两个单词押韵。例如，单词 $\text{PROL}$ 和 $\text{TARPOL}$，如果它们的重音字母都是 $\text{o}$ 或 $\text{L}$，则它们押韵；但如果重音字母分别是 $\text{RS}$，或者 $\text{PROL}$ 的重音字母是 $\text{R}$ 而 $\text{TARPOL}$ 的重音字母是 $\text{P}$，又或者 $\text{PROL}$ 的重音字母是 $\text{O}$ 而 $\text{TARPOL}$ 的重音字母是 $\text{L}$，则它们不押韵。

你找回了一份包含 $N$ 个单词的列表，这些单词可能是外星诗歌的一部分。不幸的是，你并不知道每个单词的重音字母是哪一个。你可以选择丢弃零个或多个单词，对剩下的单词分配重音字母，然后将这些单词两两配对，使得每个单词只与它的配对单词押韵，并且不与其他配对中的单词押韵。

你想知道，最多能有多少个单词可以这样被配对。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为一个整数 $N$。接下来的 $N$ 行，每行包含一个由大写英文字母组成的字符串 $W_i$，表示一个不同的单词。注意，在不同的测试用例中，相同的单词可以有不同的重音分配方式。

Output Format

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

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

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

Hint

样例解释

在样例 1 中，这两个单词可以通过合适的重音分配使其押韵，因此最大子集就是全部单词。

在样例 2 中，无论如何分配重音，都没有两个单词能押韵，因为任何两个后缀的最后一个字母都不同。因此最大子集为空，大小为 0。

在样例 3 中，如果将 CODEJAM 和 JAM 的重音都放在 J 上，将 HAM 和 NALAM 的重音都放在最后一个 A 上，将 HUM 和 NOLOM 的重音都放在 M 上，则可以使用全部单词。

在样例 4 中，任意两个单词都可以押韵，但总是通过把重音放在 I 上实现。因此，如果选取两个配对，来自不同配对的单词也会押韵。因此最多只能选取 2 个单词组成一个配对。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq W_i$ 的长度 $\leq 50$。
• $W_i$ 仅包含大写英文字母。
• 对于同一测试用例，$W_i \neq W_j$，即单词不重复。

测试点 1（10 分，可见）

• $2 \leq N \leq 6$。

测试点 2（27 分，隐藏）

• $2 \leq N \leq 1000$。

由 ChatGPT 4.1 翻译