Финальный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"B" Похожие слова
Ограничение по времени 4 секунды
Ограничение по памяти 512 мегабайт

Назовем словом непустую последовательность, состоящую из строчных букв латинского алфавита. Префиксом слова x называется слово y, которое можно получить из x удалением нуля или более последних букв x.

Назовем два слова похожими, если одно из них можно получить из другого, удалив в нем первую букву.

Дано множество слов S. Требуется найти размер максимального множества непустых слов 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
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.