eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Интересный язык

Интересный язык

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Изучая древний байтрусский язык, учёные столкнулись с любопытным явлением: в языке использовались только первые 12 букв современного латинского алфавита, из-за чего многие пары слов в языке были очень похожи друг на друга. В процессе подготовки отчёта об исследованиях учёные столкнулись со следующей задачей.

Пусть все слова языка пронумерованы начиная с 1. Обозначим i-е слово в языке как S_i, а его длину как L_i. Необходимо посчитать количество четвёрок индексов (i, j, a, b), для которых выполняются следующие условия:

  • i < j,

  • L_a > L_i,

  • L_b > L_j,

  • первые L_i символов строки S_a образуют строку S_i,

  • первые L_j символов строки S_b образуют строку S_j,

  • если из строк S_a и S_b убрать первые L_i и L_j символов соответственно, то останутся одинаковые строки.

Смотрите пример для пояснения.

Помогите учёным посчитать требуемую статистику.

Вхідні дані

В первой строке находится целое число N - количество слов в древнем байтрусском языке.

В следующих N строках находятся слова байтрусского языка по одному в строке. Все слова непустые и содержат только строчные латинские буквы от "a" до "l" включительно. Все слова различны. Суммарная длина всех слов не превосходит 10^6.

Вихідні дані

Выведите единственное число - количество четвёрок индексов, удовлетворяющих условию задачи.

Приклад

Вхідні дані #1
7
a
b
ab
bb
ac
bc
abc
Вихідні дані #1
4
Джерело Yandex.Algorithm, Online Round 3, July 22, 2013