Problem Description

Define the length of the longest common suffix of strings $A$ and $B$ as $\text{LCS}(A,B)$.

When $\text{LCS}(A,B) \ge \max(|A|,|B|)-1$, we consider strings $A$ and $B$ to be rhyming.

Given $N$ strings, find the longest possible sequence of strings (where the length of the sequence is the number of strings it contains) such that each pair of adjacent strings in the sequence rhymes.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain a string. All strings are guaranteed to be unique and the total length of all strings does not exceed $3 \times 10^6$.

Output Format

Output the maximum length of the string sequence.

Sample Input and Output

Sample Input #1

4
honi
toni
oni
ovi

Sample Output #1

3

Sample Input #2

5
ask
psk
krafna
sk
k

Sample Output #2

4

Sample Input #3

5
pas
kompas
stas
s
nemarime

Sample Output #3

1

Notes

[Sample 2 Explanation]

The sequence $\texttt{ask-psk-sk-k}$ has the maximum length of $4$.

[Sample 3 Explanation]

No two strings rhyme with each other, so any single string can form a sequence, resulting in an answer of $1$.

[Data Range and Constraints]

For $30\%$ of the data, $N \le 18$.

For $100\%$ of the data, $1 \le N \le 5 \times 10^5$.

[Translation and Original Problem]

This problem is translated from COCI 2016-2017 CONTEST #4 T5 Rima.

This problem is scored according to the original COCI settings, with a maximum score of $140$.

见题面 Input 部分

见题面 Output 部分