Description

Huahua: ... Eh~~ such a chill~~ We are going to solve the demons’ password problem (self-indulgent: maybe some demons will even use ciphers to write love letters to me and Caichong; oh ho ho, of course I’ll get more of them ^_^).

The demon clan now uses a new kind of password system. Each password is a given list of English words containing only lowercase letters, and each word has at least $1$ letter and at most $75$ letters. If, in a list consisting of one or more words, every word except the last is contained by the next word, that is, the previous word is a prefix of the next word, then the list is called a “word chain.” For example, the following words form a word chain:

• i.
• int.
• integer.

But the following words do not form a word chain:

• integer.
• intern.

Your task is to pick some words from the given list to form the longest word chain, i.e., the chain that contains the most words. Count its number of words; that number is the password.

Feng Zhi Zi: So the password is the number of words in the longest word chain...

Input Format

The first line contains the number of words $N$ ($1 \le N \le 2000$). Each of the next $N$ lines contains one word, in lexicographic order, with no duplicates.

Output Format

Output a single line with one integer, the password.

5
i
int
integer
intern
internet

4

Hint

Translated by ChatGPT 5