409339: GYM103486 F Cooking

Chiang loves cooking. There are $$$N$$$ ingredients for her to cook. Her cooking always consists of two ingredients. A dish is composed of a main ingredient and a side ingredient. Two dishes are different if and only if their main ingredients or side ingredients are different.

The dish made from the $$$i$$$-th ingredient as the main ingredient and the $$$j$$$-th ingredient as the side ingredient has a delicious value $$$W_{i,j}$$$. $$$W_{i, j}$$$ equals to the length of longest string that is both a suffix of the $$$i$$$-th ingredient's name and a prefix of the $$$j$$$-th ingredient's name. In particular, a string is both a suffix and a prefix of itself, and the empty string is a suffix and prefix of every string.

Now Chiang wants to know the sum of the delicious values of all the dishes she can cook. Please help her find out the answer.

The first line contains an integer $$$N (1 \le N \le 5 \times 10^{4})$$$, indicating the number of ingredients.

The following $$$N$$$ lines describe the name of each ingredient. The name consists of digits $$$0$$$ to $$$9$$$ only with the length no more than $$$100$$$.

Output one line contains an integer, indicating the sum of the delicious values of all the dishes.

3
10101
01010
11111

25

$$$W_{1,1}=5, W_{1,2}=4, W_{1,3}=1$$$; $$$W_{2,1}=4, W_{2,2}=5, W_{2,3}=0$$$; $$$W_{3,1}=1, W_{3,2}=0, W_{3,3}=5$$$.