Problem Description

There is a secret planet S4 inhabited by a peculiar species of animals known as Loda. The Savez Association has dispatched a team led by General Henrik to study Loda. Henrik has discovered that Loda possesses the ability of telepathy, and he wishes to recruit them into his army.

A Loda is composed of $N$ strings, with the $i$-th string denoted as $x_i$. Research indicates that the number of telepathic transmissions a Loda can perform depends on a special subsequence (not necessarily contiguous) of its constituent strings. The string $x_i$ and $x_j$ $(i < j)$ can both be in this subsequence if and only if $x_j$ starts and ends with $x_i$. The number of telepathic transmissions a Loda can perform is the length of the longest valid subsequence of its strings, and you need to determine this number.

Input Format

The first line contains an integer $N$, representing the total number of strings that make up a particular Loda.

The following $N$ lines each contain a string $x_i$, consisting only of uppercase English letters, representing the strings that constitute this Loda.

Output Format

A single line containing an integer, representing the number of telepathic transmissions this Loda can perform.

Sample Input and Output

Sample Input #1

5
A
B
AA
BBB
AAA

Sample Output #1

3

Sample Input #2

5
A
ABA
BBB
ABABA
AAAAAB

Sample Output #2

3

Sample Input #3

6
A
B
A
B
A
B

Sample Output #3

3

Notes

[Sample 1 Explanation]

One of the longest subsequences is A AA AAA.

[Sample 3 Explanation]

Strings in the subsequence are allowed to be equal, so one of the longest subsequences is A A A B B.

[Data Range]

For $100\%$ of the data, $1 \le N \le 2 \times 10^6$, $1 \le |x_i| \le 2 \times 10^6$, and guaranteed $\sum |x_i| \le 10^6$.

[Notes]

This problem's scoring is based on the original contest, with a maximum score of 120.

This problem is translated from COCI 2015-2016 CONTEST #2 T4 SAVEZ.

见题面 Input 部分

见题面 Output 部分