← 返回题目列表

Codeforces · 1551/C

C. 有趣的故事

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

斯蒂芬·奎恩想写一个故事。他是一位非常不寻常的作家,他只使用字母“a”、“b”、“c”、“d”和“e”!

为了撰写一个故事,斯蒂芬写下了 $$$n$$$ 个单词,这些单词由拉丁字母表的前 $$$5$$$ 小写字母组成。他想选择最多的字数来制作一个有趣的故事。

让故事成为不一定不同的单词序列。如果存在一个字母在故事的所有单词中出现的次数多于所有其他字母出现的次数,则该故事被称为有趣。

例如,由三个单词“bac”、“aaada”、“e”组成的故事很有趣(字母“a”出现了 $$$5$$$ 次,所有其他字母总共出现了 $$$4$$$ 次)。但由两个单词“aba”、“abcde”组成的故事则不然(没有这样的字母,它出现的次数比所有其他字母的总数还要多)。

给您一个由字母“a”、“b”、“c”、“d”和“e”组成的 $$$n$$$ 单词序列。你的任务是选择最多的数量来制作一个有趣的故事。如果无法制作一个非空故事,则输出$$$0$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 序列中单词的数量。接下来是 $$$n$$$ 行,每行都包含一个单词 - 一个由拉丁字母小写字母组成的非空字符串。序列中的单词可能是不明显的(即允许重复)。单词中只能出现字母“a”、“b”、“c”、“d”和“e”。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$;所有测试用例中所有单词的长度总和不超过 $$$4 \cdot 10^5$$$。

输出

对于每个测试用例,输出组成有趣故事的最大单词数。如果无法制作一个非空的有趣故事,则打印 0。

示例

输入 #1

6
3
bac
aaada
e
3
aba
abcde
aba
2
baba
baba
4
ab
ab
c
bc
5
cbdca
d
a
d
e
3
b
c
ca

输出 #1

3
2
0
2
3
2

注意

在示例的第一个测试用例中,所有 $$$3$$$ 单词都可以用来制作一个有趣的故事。有趣的故事是“bac aaada e”。

在示例的第二个测试用例中,$$$1$$$-st 和 $$$3$$$-rd 单词可以用来制作一个有趣的故事。有趣的故事是“aba aba”。斯蒂芬不能同时使用这三个词。

在示例的第三个测试用例中,Stephen 无法制作一个非空的有趣故事。所以答案是$$$0$$$。

在示例的第四个测试用例中,Stephen 可以使用 $$$3$$$-rd 和 $$$4$$$-th 单词来制作一个有趣的故事。有趣的故事是“c bc”。