Задача №113806. Пароли
Недавно произошла утечка информации из мега-популярной социальной сети. Среди конфиденциальной информации, попавшей в сеть, оказались и пароли всех пользователей.
Михаил, школьник, увлекающийся компьютерной безопасностью, нашёл произошедший инцидент очень интересным. Экспериментируя с социальной сетью, он нашёл ещё одну брешь в её системе безопасности! Войти в аккаунт можно, если ввести строку, содержащую настоящий пароль от аккаунта как подстроку. Например, если пользователь, чей пароль « abc » введёт « abc », « abcd » или « imaabcnema », у него успешно получиться авторизоваться в системе, но у него не получится если он введёт « axbc ».
Миша хочет узнать, сколько существует упорядоченных пар пользователей таких, что если первый пользователь введёт пароль, то он сможет войти в аккаунт второго пользователя.
В первой строчке вводится одно целое число N — число пользователей ( 1 ≤ N ≤ 20 000 ). В следующих N строках вводятся пароли пользователей, по одному в строке. Пароль содержит от 1 до 10 маленьких букв латинского алфавита.
Выведите единственное число — количество пар, которое интересует Мишу.
Решение, правильно работающее при 1 ≤ N ≤ 2 000 , будет оцениваться в 40 баллов.
Во втором примере первый пользователь может войти в аккаунт второго и третьего пользователя, а второй пользователь — в аккаунт первого и третьего пользователя.
3 aaa aa abb
1
3 x x xy
4
5 mir mirta ta ir t
6