Цікава мова#4674
У своєму дослідженні давньої байтенської мови, вчені відкрили цікаву особливість: ця мова використовує лише перші літер сучасного латинського алфавіту. Ця своєрідність призводить до того, що багато пар слів є дуже схожими. Під час підготовки наукового звіту вчені зіткнулися з наступним завданням.
Розглянемо всі слова цієї мови, пронумеровані, починаючи з . Позначимо 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,
Після видалення перших L_i символів з S_a і перших L_j символів з S_b, залишки рядків однакові.
Дивіться приклад для кращого розуміння.
Ваше завдання — допомогти вченим підрахувати цю статистику.
У першому рядку задано ціле число — кількість слів у давній байтенській мові.
Далі у наступних рядках записано по одному слову цієї мови. Кожне слово — непорожнє та складається лише з маленьких латинських літер від "a" до "l". Усі слова різні. Загальна сума довжин усіх слів не перевищує 10^6.
Виведіть єдине число — кількість четвірок індексів, які задовольняють вказаним умовам.
Приклад 1