Interesting language#4674
In their study of the ancient Bytean language, scientists discovered a fascinating aspect: the language utilizes only the first letters of the modern Latin alphabet. This peculiarity results in many pairs of words being quite similar. While preparing a research report, the scientists encountered the following task.
Consider all the words in the language, numbered starting from . Let S_i represent the -th word, with its length denoted as L_i. The task is to determine the number of quadruples of indices (i, j, a, b) that satisfy these conditions:
i < j,
L_a > L_i,
L_b > L_j,
The first L_i characters of S_a match the string S_i,
The first L_j characters of S_b match the string S_j,
After removing the first L_i characters from S_a and the first L_j characters from S_b, the remaining parts of the strings are identical.
Refer to the example for further clarification.
Your task is to assist the scientists in calculating these statistics.
The first line contains an integer , representing the number of words in the ancient Bytean language.
The following lines each contain one word of the Bytean language. Each word is non-empty and consists only of lowercase Latin letters from "a" to "l". All words are distinct. The total length of all words combined does not exceed 10^6.
Output a single integer, which is the number of quadruples of indices that meet the specified conditions.
Example 1