B. Похожие слова
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
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