问题描述

魔族使用一种新型的密码系统。每一个密码都对应一个给定的英文单词表（仅包含小写英文字母）。

如果一个由一个或多个单词组成的序列中，除了最后一个单词外，每个单词都是其后一个单词的前缀，则称该序列为一个词链。

例如：

• i $\to$ int $\to$ integer 构成一个合法的词链；
• integer $\to$ intern 不构成词链（因为 integer 不是 intern 的前缀）。

现在需要从给定的单词表中挑选出若干个单词组成一个词链，使得该词链包含的单词数量最多。请你计算并输出最长词链所包含的单词数（即密码）。

输入格式

第一行输入一个正整数 $N$，表示单词表中的单词数量。

接下来输入 $N$ 行，每行包含一个仅由小写英文字母组成的单词。输入的单词已按字典序升序排列，且互不相同。

输出格式

输出一行一个整数，表示最长词链所包含的单词数量。

样例输入 1

5
i
int
integer
intern
internet

样例输出 1

4

说明

样例 1 解释：

可以组成的最长词链为：i $\to$ int $\to$ intern $\to$ internet，共包含 $4$ 个单词。

评测数据规模

对于所有评测数据：

• $1 \leq N \leq 20000$
• 单词仅由小写英文字母组成，每个单词的长度在 $1 \sim 20$ 之间
• 输入的单词已按字典序排列，且没有重复单词