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 lp be the length of the longest common prefix of all the words in the stanza, and let ls be the length of the longest common suffix of all the words in the stanza. The beauty of the stanza is calculated as min(lp,ls)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≤n≤105.
- 1≤∑W≤105
### Example
Input:
6abcdefghijklchefworldcodeabcxyzhijklword
Output:
10
