Областная олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

Задача E. Меж двух миров

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Алан живет в мире под номером AA. Нурдаулет живет в мире под номером BB. В мире AA, если одна строка является префиксом другой, то они считаются одинаковыми. У Нурдаулета есть nn строк, он хочет узнать количество неупорядоченных пар i,ji, j таких, что Алану они покажется одинаковыми. Помогите Нурдаулету с задачей.

Обозначим s|s| как длину строки ss. Строка ss является префиксом строки tt, если s<=t|s| <= |t| и строка ss равна строке, образованной из первых s|s| символов строки tt.

Формат входного файла

В первой строке дается единственное число n(1<=n<=100000)n (1 <= n <= 100000) — количество строк. В следующих nn строках дается по одной строке sis_i. Гарантируется, что суммарная длина строк не превышает 500000500000.

Формат выходного файла

Выведите единственное число — ответ на задачу.

Примеры

Вход

3
ab
abc
ab

Выход

3