← 返回题目列表

Codeforces · 856/B

B. 相似词

中文机器翻译题面 查看原题

让我们将非空的小写英文字母序列称为单词。单词x的前缀是可以从x中删除x的零个或多个最后字母而获得的单词y。

如果两个单词中的一个可以通过删除其第一个字母从另一个单词中获得,我们称两个单词相似。

给你一组 S 个单词。找到非空词集合 X 的最大可能大小,使其满足以下条件:

- X 的每个单词都是 S 中某个单词的前缀;
- X没有相似的词。

输入

输入数据包含多个测试用例。输入数据的第一行包含一个整数 t — 测试用例的数量。测试用例的描述如下。

每个描述的第一行包含一个整数 n — 集合 S 中的单词数量 (1 ≤ n ≤ 106)。接下来的 n 行每一行都包含一个非空单词——S 的元素。S 中的所有单词都不同。

保证一次输入数据中所有字的总长度不超过106。

输出

对于每个测试用例,打印一行,其中包含一个整数 m — X 可以包含的最大单词数。

示例

输入 #1

2
3
aba
baba
aaab
2
aa
a

输出 #1

6
1