Description

Adrian likes rhyme in poetry. He thinks two words rhyme if and only if the length of their longest common suffix is at least the length of the longer word minus one. That is, words A and B rhyme if and only if $\operatorname{LCS}(A,B) \ge \max(|A|,|B|)- 1$. (Here, $\operatorname{LCS}$ is the abbreviation for the longest common suffix.)

Now Adrian has $N$ words. He wants to select as many words as possible to form a sequence such that any two adjacent words in the sequence rhyme.

Input Format

The first line contains an integer $N$.

Each of the next $N$ lines contains a string consisting of lowercase English letters, representing a word. All words are distinct.

Output Format

Output a single line with one integer, the length of the longest word sequence.

5
ask
psk
k
krafna
sk

4

Hint

[Sample Explanation]

One longest word sequence is ask-psk-sk-k.

[Constraints]

30% of the testdata: $1 \le N \le 20$, and the sum of word lengths does not exceed $3000$.

100% of the testdata: $1 \le N \le 5 \times 10^5$, and the sum of word lengths does not exceed $3 \times 10^6$.

Translated by ChatGPT 5