Longest Word Chain

You are given a list of words that contain only lowercase English letters. Each word has a length of at least $1$ and at most $75$. A word chain is a list of words (with one or more words) in which every word except the last one is a prefix of the word that immediately follows it.

For example, the words:

• i
• int
• integer

form a valid word chain since i is a prefix of int and int is a prefix of integer.

However, the words:

• integer
• intern

do not form a valid word chain because integer is not a prefix of intern.

Your task is to select some words from the given list and arrange them in such a way that they form the longest possible word chain (i.e. the chain that contains the maximum number of words). The password is simply the total number of words in this longest chain.

Input Constraints: Each word consists only of lowercase letters with a length between 1 and 75.

inputFormat

The input begins with an integer $n$ representing the number of words. Each of the next $n$ lines contains a single word.

Input Format:
  n
  word1
  word2
  ...
  wordn

outputFormat

Output a single integer that is the length of the longest word chain that can be formed.

Output Format:
  answer

sample

3
i
int
integer

3