Description

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

When $\text{LCS}(A,B) \ge \max(|A|,|B|)-1$, we say that the two strings $A, B$ rhyme.

Given $N$ strings, you need to form a longest possible sequence of strings (the sequence length is the number of strings in it) such that every pair of adjacent strings in the sequence rhymes.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain one string. It is guaranteed that all strings are distinct, consist of lowercase letters, and the total length does not exceed $3 \times 10^6$.

Output Format

Output the maximum possible length of the string sequence.

4
honi
toni
oni
ovi

3

5
ask
psk
krafna
sk
k

4

5
pas
kompas
stas
s
nemarime

1

Hint

[Explanation of Sample 2]

The string sequence $\texttt{ask-psk-sk-k}$ has the maximum length, which is $4$.

[Explanation of Sample 3]

No two strings rhyme, so any single string can form a sequence by itself. The answer is $1$.

[Constraints]

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

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

[Hints and Notes]

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

The score of this problem follows the original COCI setting, with a full score of $140$.

Translated by ChatGPT 5