410312: GYM104008 I Invincible Hotwheels

Yukari is an elusive youkai (monster) who can manipulate boundaries. Recently Yukari is in a bad temper, and when she hears someone saying something she does not like (for example, "Yukari is thousands of years old"), she will be angry and beat the person from behind. Reimu has been bothered by her for a while because she does not know which words make Yukari unhappy. Even saying some common words like "cooooooooooooooooooooooool", "I want to eat noodles", or "invincible hotwheels" will be beaten by Yukari.

To avoid angering Yukari, Reimu finds out $$$n$$$ possible words Yukari may dislike, numbered from $$$1$$$ to $$$n$$$. Each word is a string containing only lowercase English letters. However, some redundant (unnecessary) words may contain other words. For example, if "iwanttoeatnoodles" and "noodles" are both possible words, then the former is redundant.

Reimu wants to estimate how many redundant relations are among the $$$n$$$ words. Formally, let $$$s_i$$$ denotes the $$$i$$$-th word. Reimu wants to know that, how many tuples of $$$(i,\ j,\ k)$$$ ($$$1\le i,\ j,\ k\le n$$$; $$$i, j, k$$$ are pairwise distinct) satisfying following contidions: $$$s_i$$$ is a substring of $$$s_j$$$, and $$$s_j$$$ is a substring of $$$s_k$$$. Also, there must not be another $$$j'$$$ which is not equal to $$$i, j$$$ or $$$k$$$, such that $$$s_i$$$ is also a substring of $$$s_{j'}$$$, and $$$s_{j'}$$$ is also a substring of $$$s_k$$$.

Reimu asked you for help her calculating the number of such tuples.

The first line of input contains one positive integer $$$n$$$ ($$$1\le n\le 10^6$$$), denoting the number of words.

Then follows $$$n$$$ lines. The $$$i$$$-th line contains a non-empty string $$$s_i$$$ consisting of lowercase letters, denoting the $$$i$$$-th word. It is guaranteed that all the words are distince and $$$\sum_{i=1}^n |s_i| \le 2\times 10^6$$$ holds.

Output one integer - the answer described in the statement.

8
wwwsoupunetcom
wwwsoupunet
soupunet
punetcom
punet
pun
net
n

6

4
a
aa
aaa
aaaa

2

5
bc
cbcb
cbca
cbc
c

3

For the first example, the valid tuples are $$$(3,2,1)$$$, $$$(5,3,2)$$$, $$$(6,5,3)$$$, $$$(6,5,4)$$$, $$$(7,5,3)$$$ and $$$(7,5,4)$$$.