Little Adrian is a fan of rhyme. He believes that two words rhyme if and only if their longest common suffix is as long as the longer of the two words, or shorter than the longer word by ~1~. In other words, ~A~ and ~B~ rhyme if and only if it holds ~LCS(A, B) \ge \max(|A|, |B|) - 1~.

One day, while reading a collection of short stories, he decided to compose the longest possible sequence of words such that each two consecutive words rhyme. Each word from the sequence can appear only once.

Adrian has grown tired of this task, so he decided to go back to reading, and is asking you to solve this task instead of him.

Input Specification

The first line of input contains the integer ~N~ ~(1 \le N \le 500\,000)~.

Each of the following ~N~ lines contains one word consisting of lowercase letters of the English alphabet. All words are mutually distinct, and their total length is at most ~3\,000\,000~.

Output Specification

You must output the length of the longest sequence.

Scoring

In test cases worth ~30\%~ of points, it will hold ~N \le 18~.

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

Explanation for Sample Output 2

The only possible sequence is ask-psk-sk-k.

Sample Input 3

5
pas
kompas
stas
s
nemarime

Sample Output 3

1

Explanation for Sample Output 3

No two words rhyme.