Longest Word Chain

You are given a list of lowercase English words. A word chain is a sequence of words where every word in the sequence (except the first one) can be formed by adding exactly one letter to the previous word (the letters may be inserted at any position). Formally, for two words (w_1) and (w_2) with (|w_2| = |w_1| + 1), we say that (w_2) is a successor of (w_1) if there exists an index (i) ((0 \leq i \leq |w_2| - 1)) such that removing the (i)-th character from (w_2) yields (w_1). Your task is to compute the length of the longest possible word chain that can be formed from the given list of words. The chain does not have to use all the words.

inputFormat

The input is given in stdin. The first line contains a single integer (n) representing the number of words. The second line contains (n) space-separated words.

outputFormat

Output to stdout a single integer, the length of the longest word chain possible.## sample

6
a b ba bca bda bdca

4