Интересный язык
Изучая древний байтрусский язык, учёные столкнулись с любопытным явлением: в языке использовались только первые 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.
Выходные данные
Выведите единственное число - количество четвёрок индексов, удовлетворяющих условию задачи.