题目描述

给定一个仅包含小写字母的英文单词表，其中每个单词最多包含 50 个字母。

如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。例如下面的单词组成了一个词链：

i

int

integer

而下面的单词不组成词链：

integer

intern

请在给定的单词表中取出一些词，组成最长的词链。最长的词链就是包含单词数最多的词链。

数据保证给定的单词表中，单词互不相同。

输入格式

第一行一个整数（n ≤ 1000），表示单词表中单词数。

接下来 n 行每行一个单词。

输出格式

一个整数，表示最长词链长度。

输入样例 #1

5
i
integer
internet
intern
int

输出样例 #1

4

输入样例 #2

8
abc
abd
a
ac
ab
abcde
abcf
abcfgh

输出样例 #2

5

输入样例 #3

5
aabad
cceabbaedaccaaaeeedacbaacdbeabcaaaedde
dcdebeecdbbbeedacbeebeecaaedbcddccbccec
acde
ebeccbeab

输出样例 #3

1

数据范围与约定

n ≤ 1000；每个单词最多包含 50 个字母；单词互不相同。