Loda Mind Transmission

A secret planet S4 is inhabited by a peculiar creature called Loda. Each Loda is composed of N strings: x₁, x₂, ..., x_N. Research has shown that the number of mind transmissions a Loda can perform is equal to the length of the longest subsequence of its strings satisfying the following condition:

For any two strings x_i and x_j (i < j) in the subsequence, it must hold that x_j starts with and ends with x_i. In mathematical notation, using LaTeX, for a valid adjacent pair in the subsequence, we require:

$$\text{prefix}(x_j, |x_i|)=x_i \quad\text{and}\quad \text{suffix}(x_j, |x_i|)=x_i $$

Your task is to determine the maximum mind transmissions a Loda can perform, i.e. compute the length of the longest valid subsequence of strings.

inputFormat

The input consists of multiple lines. The first line contains an integer N denoting the number of strings. The following N lines each contain one non-empty string x_i.

You can assume that all strings consist of standard ASCII characters.

outputFormat

Output a single integer representing the length of the longest valid subsequence where for any two strings x_i and x_j in the subsequence with i < j, x_j has x_i as both its prefix and suffix.

sample

3
a
aba
ababa

3

</p>