Lweb is facing a mountain of English words and has fallen into deep contemplation: "How can I finish learning these quickly so I can go play Sanguosha?" At this moment, the wise Teacher Feng drifts over from afar and gives Lweb a planner and a large jar of pickled peppers. The planner looks like this:
| Index | Word |
|---|---|
| 1 | |
| 2 | |
| $\dots$ | |
| $n-2$ | |
| $n-1$ | |
| $n$ |
Then, Teacher Feng tells Lweb, "I know you have a total of $n$ words to learn. Now, we fill in the planner from top to bottom. For a word at index $x$ (where indices $1 \dots x-1$ have already been filled):
1) If there exists a word that is a suffix of the current word, and it has not yet been filled into the table, he must eat $n \times n$ pickled peppers to learn it; 2) If all its suffixes have already been filled into the table, and none of the words at positions $1 \dots x-1$ are its suffixes, then you only need to eat $x$ pickled peppers to memorize it; 3) If all its suffixes have already been filled into the table, and there exist words at positions $1 \dots x-1$ that are its suffixes, let $y$ be the maximum index among all such suffixes. Then you only need to eat $x-y$ pickled peppers to memorize it."
Lweb is a strange child who goes berserk when eating spicy food, so please help Lweb find an optimal way to fill in the words such that the total number of pickled peppers he eats to memorize all $n$ words is minimized.
Input
The input contains an integer $n$, representing the number of words Lweb needs to learn. The next $n$ lines each contain a word (consisting of lowercase letters, and it is guaranteed that all words are distinct).
Output
The minimum number of pickled peppers Lweb eats.
Examples
Input 1
2 a ba
Output 1
2
Constraints
10% of the data: $1 \le n \le 8$, total length of all characters $1 \le |len| \le 11000$. 30% of the data: $1 \le n \le 20$, total length of all characters $1 \le |len| \le 310000$. 100% of the data: $1 \le n \le 100000$, total length of all characters $1 \le |len| \le 510000$.