题目描述

有一个秘密行星 S4 居住着一种奇特的动物，它们的学名是 Loda。Savez 协会派出了一个由 Henrik 将军领导的小组来研究 Loda。Henrik 发现，Loda 有心灵传输的能力，他想在他的军队里雇佣他们。

一只 Loda 由 $N$ 个字符串组成，其中第 $i$ 个字符串记为 $x_i$。研究表明，Loda 能进行的心灵传输次数取决于组成它的字符串的一个特殊子序列（不一定是连续的）。字符串 $x_i$ 和 $x_j$ $(i<j)$ 都可以在该子序列中，当且仅当字符串 $x_j$ 以 $x_i$ 开头并以 $x_i$ 结尾。一只 Loda 可以进行的心灵传输次数是组成它的字符串的合法的最长子序列的长度，而你就需要确定它可以进行心灵传输的次数。

输入格式

第一行一个整数 $N$，表示组成某一只 Loda 的字符串总数。

接下来 $N$ 行，每行一个仅由大写英文字母构成的字符串 $x_i$，表示构成这一只 Loda 的字符串。

输出格式

一行一个整数，表示这只 Loda 可以进行心灵传输的次数。

5
A
B
AA
BBB
AAA

3

5
A
ABA
BBB
ABABA
AAAAAB

3

6
A
B
A
B
A
B

3

提示

【样例 1 解释】

一个最长的子序列为 A AA AAA。

【样例 3 解释】

子序列中的字符串允许相等，因此一个最长的子序列为 A A A B B。

【数据范围】

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

【说明】

本题数据点得分依原题，满分 120。

题目译自 COCI 2015-2016 CONTEST #2 T4 SAVEZ。