Password Substring Hacking

Recently, there has been a breach of user information from the mega-popular social network Secret Network. Among the confidential information are the passwords of all users.

Mihael, a young student who has been exploring computer security lately, found the whole thing really interesting. While experimenting with the social network, he discovered another security breach! When you input any string of characters that contains a substring equal to the actual password, the login will be successful. For example, if a user whose password is abc inputs one of the strings abc, abcd or imaabcnema, the system will successfully log him in, whereas the login will fail for axbc.

Mihael wants to know how many ordered pairs of different users exist such that the first user, using their own password, can login as the second user. In other words, given a list of user passwords, count the number of ordered pairs \((i, j)\) (where \(i \neq j\)) such that the password of user \(i\) contains the password of user \(j\) as a substring.

inputFormat

The first line of input is an integer \(n\) (\(2 \leq n \leq 1000\)), the number of users. Then follow \(n\) lines, each containing a non-empty string representing the user password. The passwords consist of lowercase letters only.

outputFormat

Output a single integer representing the number of ordered pairs of distinct users \((i, j)\) such that the password of user \(i\) contains the password of user \(j\) as a substring.

sample

3
abc
abcd
b

3