Problems
Интересный язык
Интересный язык
Изучая древний байтрусский язык, учёные столкнулись с любопытным явлением: в языке использовались только первые \textbf{12} букв современного латинского алфавита, из-за чего многие пары слов в языке были очень похожи друг на друга. В процессе подготовки отчёта об исследованиях учёные столкнулись со следующей задачей.
Пусть все слова языка пронумерованы начиная с \textbf{1}. Обозначим \textbf{i}-е слово в языке как \textbf{S_i}, а его длину как \textbf{L_i}. Необходимо посчитать количество четвёрок индексов \textbf{(i, j, a, b)}, для которых выполняются следующие условия:
\begin{itemize}
\item \textbf{i} < \textbf{j},
\item \textbf{L_a} > \textbf{L_i},
\item \textbf{L_b} > \textbf{L_j},
\item первые \textbf{L_i} символов строки \textbf{S_a} образуют строку \textbf{S_i},
\item первые \textbf{L_j} символов строки \textbf{S_b} образуют строку \textbf{S_j},
\item если из строк \textbf{S_a} и \textbf{S_b} убрать первые \textbf{L_i} и \textbf{L_j} символов соответственно, то останутся одинаковые строки.
\end{itemize}
Смотрите пример для пояснения.
Помогите учёным посчитать требуемую статистику.
\InputFile
В первой строке находится целое число \textbf{N} - количество слов в древнем байтрусском языке.
В следующих \textbf{N} строках находятся слова байтрусского языка по одному в строке. Все слова непустые и содержат только строчные латинские буквы от "\textbf{a}" до "\textbf{l}" включительно. Все слова различны. Суммарная длина всех слов не превосходит \textbf{10^6}.
\OutputFile
Выведите единственное число - количество четвёрок индексов, удовлетворяющих условию задачи.
Input example #1
7 a b ab bb ac bc abc
Output example #1
4
Example description: В первом примере подходят следующие четвёрки индексов: (1, 2, 3, 4), (1, 2, 5, 6), (1, 3, 5, 7), (2, 3, 6, 7). Во втором примере подходят следующие четвёрки индексов: (1, 3, 3, 5), (2, 4, 4, 6), (3, 4, 7, 8), (2, 6, 6, 8).