Longest String Chain

Choose a word chain from the word list, where each next word is obtained from the previous one by inserting exactly one letter while keeping the order of the other letters. Find the number of words in the longest chain. Words of the same length cannot be predecessors of each other.

输入格式

The first line contains the number of words n, followed by one word per line. Original bounds 1≤n≤1000, each word has length 1..16, all lowercase English; duplicate words are allowed.

输出格式

Output a single integer answer.

样例 1

输入：

6
a
b
ba
bca
bda
bdca

输出：

4

样例 2

输入：

5
xbc
pcxbcf
xb
cxbc
pcxbc

输出：

5

样例 3

输入：

2
abcd
dbqca

输出：

1

样例说明

The outputs of the three public examples are, in order: 4; 5; 1. Checked by independent enumeration or direct simulation.