C. Интересный рассказ
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стивен Квин хочет написать новый рассказ. Вы знаете, он очень необычный писатель — Стивен использует только буквы 'a', 'b', 'c', 'd' и 'e'!

Чтобы написать рассказ, Стивен выписал $$$n$$$ слов, состоящих из первых $$$5$$$ строчных букв латинского алфавита. Из них он хочет выбрать максимальное количество слов таким образом, чтобы получился интересный рассказ.

Рассказ представляет собой список слов, необязательно различных. Рассказ называется интересным, если существует буква, которая встречается во всех входящих в него словах большее количество раз, чем все остальные буквы латинского алфавита вместе взятые.

Например, рассказ, состоящий из слов «bac», «aaada», «e», является интересным (буква «a» встречается в словах рассказа всего $$$5$$$ раз, остальные — $$$4$$$), а рассказ, состоящий из слов «aba», «abcde» — нет (не существует буквы, встречающейся во всех словах рассказа большее число раз, чем все остальные вместе взятые).

Вам дан список из $$$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.

Пример
Входные данные
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
Выходные данные
3
2
0
2
3
2
Примечание

В первом наборе входных данных примера все $$$3$$$ слова могут быть использованы одновременно, чтобы составить интересный рассказ. Рассказ будет иметь вид «bac aaada e».

Во втором наборе входных данных примера $$$1$$$-е и $$$3$$$-е слова могут быть использованы для составления интересного рассказа. Рассказ будет иметь вид «aba aba». Заметим, что все три слова одновременно использовать нельзя.

В третьем наборе входных данных примера автор не может составить непустой интересный рассказ. Поэтому ответ равен $$$0$$$.

В четвертом наборе входных данных примера $$$3$$$-е и $$$4$$$-е слова могут быть использованы для составления интересного рассказа. Рассказ будет иметь вид «c bc».