题目描述

你被给予了 $n$ 个字符串，每个字符串仅包含小写字母。

现在你需要在这 $n$ 个字符串中选出一个子序列（可以全选），并且满足以下条件：

$1.$ 在这个子序列中前一个字符串是后一个字符串的前缀（字符串相同也算作前缀）。

$2.$ 子序列的长度最大。

你需要求出满足题意的子序列，并输出它的长度。

输入格式

第一行为单词表中的字符串个数 $N$（$1 \le N \le 200000$）。

下面 $N$ 行，每行有一个字符串。

输出格式

输出共一行，一个整数，表示满足题意的子序列的长度。

样例 #1

样例输入 #1

5
i
int
integer
intern
internet

样例输出 #1

4

样例 #2

样例输入 #2

11
a
ab
abba
abd
acd
acdd
acddq
acddqw
adcad
adcadq
aef

样例输出 #2

5

数据范围

对于 $20\%$ 的数据保证，$n \le 20$。

对于 $60\%$ 的数据保证，$n \le 2000$。

对于所有数据保证，$n \le 100000$，所有字符串的总长度 $L \le 10^7$，单个字符串长度 $\le 200$。