Given a set $\{s_i\}$ consisting of strings containing only lowercase letters, you need to select some strings from the set and choose a suitable order to concatenate them into a new string. Let this new string be $S$. The problem setter does not want $S$ to contain the subsequence luolikong, meaning there does not exist a set of positions $\{pos_i\}$ in $S$ such that:

1. The size of the set is 9 and $1 \le pos_i \le |S|$.
2. For all $1 \le i \le 8$, $pos_i < pos_{i+1}$.
3. For the string $t$ of length 9 where $t_i = S_{pos_i}$, $t = \text{luolikong}$.

The problem setter does not want to explain the reason for this.

You only need to calculate the maximum possible length of $S$.

Input

The first line contains an integer $n$ ($1 \le n \le 5000$), representing the size of the set $\{s_i\}$.

The next $n$ lines each contain a string $s_i$ ($1 \le |s_i| \le 5 \times 10^5$, $\sum |s_i| \le 5 \times 10^5$).

Output

Output a single integer representing the maximum possible length of $S$.

Examples

Input 1

5
zhongzhikong
luo
likelisi
kluikong
likuong

Output 1

31

Note

One valid concatenation scheme is: zhongzhikong kluikong luo likelisi.

It is easy to prove that there is no other concatenation scheme that results in a string length greater than 31 while not containing the subsequence luolikong.