给定一个由N个由大写字母构成的字符串的序列。现在要在序列中按顺序找出一个最长的子序列（不一定连续），子序列中任意两元素满足以下关系。假设元素i为字符串Xi,元素j为字符串xj,i < j,则xj要与xi有相同的前缀和后缀，反之xi不一定与xj有相同的前缀和后缀。输出最长子序列的长度。
输入：
第一行一个正整数N，表示字符串序列的个数。
接下来N行，每行一个字符串。输入保证字符串总长度小于200万。
输出：一行一个数，表示子序列的长度。
40%的数据($1<= N<= 500$).

Input
5
A
B
AA
BBB
AAA
Output
3
input
5
A
ABA
BBB
ABABA
AAAAAB
Output
3
input
6
A
B
A
B
A
B
Output
3

【数据范围】

对于 $100\%$ 的数据，$1\le N \le 2\times 10^6，1\le |x_i| \le 2\times 10^6$，保证 $\sum |x_i|\le10^6$。