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