Longest Word Chain

You are given a list of unique words. Your task is to determine the length of the longest chain of words that can be formed under the following conditions:

• Each word in the chain is exactly one character longer than its predecessor.
• Every word in the chain (except the first) is formed by inserting exactly one character into the previous word at any position, so that the previous word appears as a subsequence of the current word.

For example, given the words ["a", "b", "ba", "bca", "bda", "bdca"], one of the longest chains is "a" → "ba" → "bda" → "bdca" with a length of 4.

You need to read the input from standard input (stdin) and print the result to standard output (stdout).

inputFormat

The input consists of multiple lines:

1. The first line contains a single integer n representing the number of words.
2. The following n lines each contain one word.

It is guaranteed that all words are unique and consist of lowercase letters only.

outputFormat

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

6
a
b
ba
bca
bda
bdca

4