L. Lady Gaga and the Echoing Coefficient
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lady Gaga is a complete artist: unmatched in performances, extremely versatile, and full of diverse artistic references. Throughout her career, she has established herself as one of the most essential figures in the history of pop music, and as a voice for many who cannot find their own. To the delight of the Little Monsters, she constantly reinvents herself, always leaving her legion of fans eager for her next steps.

To further improve her songwriting skills, Lady Gaga studied a property of song lyrics called the Echoing Coefficient, which is simply the sum of the values of all Echoing Segments of a lyric. An Echoing Segment is a passage of a lyric that can be represented as the same passage repeated twice, and its value is the product of the number of lines that compose it and the total number of characters in those lines.

As an example, the following excerpt from Bad Romance is an Echoing Segment (because it can be represented as the repetition of the first three lines):

Oh-oh-oh-oh-oh

Oh-oh-oh-oh-oh-oh-oh

Caught in a bad romance

Oh-oh-oh-oh-oh

Oh-oh-oh-oh-oh-oh-oh

Caught in a bad romance

Formally, the lyrics of a song can be represented as a list $$$L$$$ of lines, where the $$$i$$$-th line can be represented as a string $$$L_i$$$. A passage of a lyric is a contiguous sublist of $$$L$$$ — if it is composed of all lines from the $$$i$$$-th to the $$$j$$$-th (with $$$j \geq i$$$), it is denoted by $$$L_i^j$$$. Thus, an Echoing Segment of $$$L$$$ is a passage $$$L_i^j$$$ such that there exists some list of lines $$$V$$$ for which $$$L_i^j = V + V$$$, where $$$+$$$ represents the list concatenation operation. Therefore, the value of an Echoing Segment $$$L_i^j$$$ is given by $$$(j-i+1) \cdot \sum_{k=i}^j |L_k|$$$, where $$$|L_k|$$$ is the length of the string representing the $$$k$$$-th line. Finally, the Echoing Coefficient of a lyric is the sum of the values of all Echoing Segments of that lyric.

In her studies, Lady Gaga wants to analyze song lyrics and their respective Echoing Coefficients. To make this process more convenient, she asked her team for a program that receives a simplified song lyric (without uppercase letters, punctuation, or special characters) and prints the Echoing Coefficient of that lyric.

Help Mother Monster with a program that performs this calculation efficiently!

Input

The first line of the input contains an integer $$$N$$$: the number of lines in the song lyric $$$(1 \leq N \leq 5 \cdot 10^4)$$$.

Each of the next $$$N$$$ lines contains a string $$$L_i$$$, representing the $$$i$$$-th line of the lyric $$$(1 \leq |L_i| \leq 25)$$$. It is guaranteed that $$$L_i$$$ contains only lowercase characters from $$$a$$$ to $$$z$$$.

Output

Print, on a single line, a single value: the Echoing Coefficient of the song lyric represented by the input.

Examples
Input
14
ohohohohoh
ohohohohohohoh
caughtinabadromance
ohohohohoh
ohohohohohohoh
caughtinabadromance
raraahahah
romaromama
gagaohlala
wantyourbadromance
raraahahah
romaromama
gagaohlala
wantyourbadromance
Output
1284
Input
12
cantreadmycantreadmy
nohecantreadmypokerface
shesgotmelikenobody
cantreadmycantreadmy
nohecantreadmypokerface
shesgotmelikenobody
cantreadmycantreadmy
nohecantreadmypokerface
shesgotmelikenobody
cantreadmycantreadmy
nohecantreadmypokerface
shesgotmelikenobody
Output
8184
Input
2
a
aaa
Output
0
Input
4
a
b
a
b
Output
16
Note

Note that the definition of an Echoing Segment refers to the concatenation of lists, not to the concatenation of all strings in the lists. Therefore, in the third sample test case, there are no Echoing Segments: even though "a" $$$+$$$ "aaa" $$$=$$$ "aaaa" and "aaaa" can be represented as "aa" $$$+$$$ "aa", the list {"a", "aaa"} cannot be represented as the concatenation of two equal lists.