Marisa is writing a poem, and she knows $n$ words.
A poem consists of several stanzas, and each stanza consists of several words (at least two). A word can appears multiple times. If a word appears $k$ times, then Marisa can use that word no more than $k$ times. Marisa also does not necessarily use all the words she knows.
For each stanza, let $l_p$ be the length of the longest common prefix of all the words in the stanza, and let $l_s$ be the length of the longest common suffix of all the words in the stanza. The beauty of the stanza is calculated as $min(l_p, l_s)^2$.
Find a way to write a poem, consisting of several stanzas, so that the total beauty of the stanzas is maximized.
### Input
- The first line contains an integer $n$.
- The next $n$ lines each contain a string $W$, which is a word that Marisa knows.
### Output
- Print the maximum beauty value.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le \sum{W} \le 10^5$
### Example
Input:
```
6
abcdefghijkl
chef
world
code
abcxyzhijkl
word
```
Output:
```
10
```
