cho.sh

Passwords

Count ordered pairs of distinct passwords where one string is a substring of the other, treating the passwords as a multiset of short strings.

Medium5String matchingHash mapTrieNo attempts yetTime limit1sMemory limit64 MB

Problem

User information leaked from the popular social network Secret Network. The leaked data holds the passwords of every user.

Mihael, a student who has been studying computer security, found the whole affair interesting. While poking around the social network he found one more hole. If you type any string that contains a substring equal to the real password, the login succeeds. For example, a user whose password is abc is logged in after typing abc, abcd or imaabcnema, while axbc fails.

Mihael wants to know how many ordered pairs of two different users there are such that the first user, typing their own password, can log in as the second user.

Input

The first line contains the number of users NN (1≤N≤200001 \le N \le 20000). Each of the next NN lines contains one user's password. A password is a string of 1 to 10 lowercase letters of the English alphabet.

Output

Print the number of ordered pairs described in the statement on the first line.

Note

Consider three users whose passwords are x, x and xy in that order. The first user can log in as the second, and the second can log in as the first. The third user can log in as the first and also as the second. The answer is therefore 4.