H. Экзамен
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этом году в Конохе вновь проводится экзамен на звание Чунина, и в нем участвуют $$$n$$$ ниндзя с именами $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$. Все имена участников различны. Один из этапов экзамена — сражения между участниками. В этом году руководство Конохи решило, что определять, кто с кем сражается, будут по-новому. Ниндзя $$$i$$$ сражается с ниндзя $$$j$$$, если выполнены три правила:

  • $$$i \neq j$$$;
  • $$$s_{j}$$$ — подстрока $$$s_{i}$$$;
  • не существует $$$k$$$, отличного от $$$i$$$ и $$$j$$$ такого, что $$$s_{j}$$$ — подстрока $$$s_{k}$$$, а $$$s_{k}$$$ — подстрока $$$s_{i}$$$.

Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

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

Входные данные

Первая строка содержит натуральное число $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$) — число участников экзамена.

Следующие $$$n$$$ строк содержат имена участников. Все имена непустые, различны и состоят из строчных латинских букв. Суммарная длина всех имен не превосходит $$$10^6$$$.

Выходные данные

Необходимо вывести единственное число — количество сражений на экзамене в этом году.

Примеры
Входные данные
5
hidan
dan
hanabi
bi
nabi
Выходные данные
3
Входные данные
4
abacaba
abaca
acaba
aca
Выходные данные
4
Примечание

В первом примере hidan сражается с dan, а hanabi сражается с nabi, который также сражается с bi. Ниндзя с именами hanabi и bi не сражаются, поскольку есть ниндзя с именем nabi, из-за которого для этой пары не выполняется третье условие.

Во втором примере сражения происходят между abacaba и acaba, abacaba и abaca, acaba и aca, abaca и aca.