Назовем словом непустую последовательность, состоящую из строчных букв латинского алфавита. Префиксом слова x называется слово y, которое можно получить из x удалением нуля или более последних букв x.
Назовем два слова похожими, если одно из них можно получить из другого, удалив в нем первую букву.
Дано множество слов S. Требуется найти размер максимального множества непустых слов X, удовлетворяющего следующим условиям:
Входные данные содержат несколько тестов. Первая строка входных данных содержит число t — количество тестов. Далее следуют описания тестов.
Первая строка каждого описания содержит целое число n — количество слов в множестве S (1 ≤ n ≤ 106). В каждой из следующих n строк содержится по одному непустому слову — элементы множества S. Все слова в S различны.
Гарантируется, что суммарная длина всех слов во входных данных не превосходит 106.
Для каждого теста выведите на отдельной строке число m — размер максимального искомого множества X.
2
3
aba
baba
aaab
2
aa
a
6
1
Название |
---|