Problem Description

There is a secret planet S4 where a strange animal lives, whose scientific name is Loda. The Savez association sent a team led by General Henrik to study Loda. Henrik discovered that Loda has the ability of telepathic transmission, and he wants to hire them for his army.

One Loda consists of $N$ strings, and the $i$-th string is denoted as $x_i$. Research shows that the number of telepathic transmissions a Loda can perform depends on a special subsequence (not necessarily contiguous) of the strings that make it up. Strings $x_i$ and $x_j\ (i<j)$ can both be in the subsequence if and only if $x_j$ starts with $x_i$ 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 how many telepathic transmissions it can perform.

Input Format

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

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

Output Format

Output one integer in a single line, indicating how many telepathic transmissions this Loda can perform.

5
A
B
AA
BBB
AAA

3

5
A
ABA
BBB
ABABA
AAAAAB

3

6
A
B
A
B
A
B

3

Hint

[Sample 1 Explanation]

One longest subsequence is A AA AAA.

[Sample 3 Explanation]

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

[Constraints]

For $100\%$ of the testdata, $1\le N \le 2\times 10^6，1\le |x_i| \le 2\times 10^6$, it is guaranteed that $\sum |x_i|\le 2\times 10^6$.

[Note]

The scoring of test cases follows the original problem, with a full score of 120.

Translated from COCI 2015-2016 CONTEST #2 T4 SAVEZ.

Translated by ChatGPT 5