Longest Word Chain Game

Given an English word list where each word consists of lowercase letters without any special symbols, your task is to form the longest possible word chain following the rules below:

• The next word in the chain must have exactly one more letter than the previous word.
• Every letter in the previous word must appear in the next word with at least the same frequency.

For example, consider the word list:

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc

A valid chain is:

ab
bar
crab
cobra
carbon
carbons

The objective is to determine the maximum length of a valid word chain. Note that a single word is considered a valid chain of length 1 in case no extension is possible.

inputFormat

The first line contains an integer n, the number of words.

The following n lines each contain a word.

outputFormat

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

sample

3
a
ab
abc

3