You are given a list of strings, each consisting of lowercase Latin letters. We will call a string , consisting of lowercase Latin letters and the character '#', a reference string if, for every string in the list, it is possible to choose some index in such that ≠ ‘#’ and selecting all indices from to the next occurrence of '#' (not inclusive) will result in the respective string. The reference string should always end with the character ‘#’.
Write a program that determines the length of the shortest reference string that satisfies the above condition, given the list of strings.
Input
The first line of the input contains a single integer, n (), representing the number of strings in the list.
The following n lines contain the strings. Each string consists of lowercase Latin letters and has a length of at most 10.
Output
Output a single integer, representing the length of the shortest reference string that satisfies the condition.
Examples
Input
Output
6
found
profound
ground
round
wound
und
22
3
ab
bc
cd
9
Explanation
In the first example one of the shortest reference strings is the string ‘ground#profound#wound# ’
In the second example one of the shortest reference strings is the string ‘ab#bc#cd#’