太阳系中有八颗行星和一颗矮行星。鲜为人知的是，存在一个秘密星球 S4，居住着类似熊的小生物，代号为 Lodas。尽管这一事实对公众隐瞒得很好，但 Savez 协会还是派出了一支由 Henrik 将军带领的队伍去研究 Lodas。研究发现 Lodas 具有瞬间移动的能力，将军想雇佣他们加入他的军队。

一个 Lod 由 $N$ 个字符串组成，其中第 $i$ 个字符串记为 $x_i$。研究表明，一个 Loda 可以进行的瞬间移动次数取决于这些字符串的一个特殊子序列（不一定连续）。字符串 $x_i$ 和 $x_j$（$i < j$）可以同时出现在该子序列中，当且仅当字符串 $x_j$ 既以字符串 $x_i$ 开头，又以字符串 $x_i$ 结尾。一个 Loda 可以进行的瞬间移动次数是上述最长子序列的长度。

请确定瞬间移动的次数。

输入格式

输入的第一行包含整数 $N$，表示字符串的数量。

接下来的 $N$ 行，每行包含一个由大写英文字母组成的字符串。

输入数据保证所有字符串的总字符数少于 $2\,000\,000$。

输出格式

输出的第一行也是唯一一行，包含一个 Loda 可以进行的瞬间移动的最大次数。

数据范围

在占总分 40% 的测试数据中，满足 $1 \le N \le 500$。

样例

输入样例 1

5
A
B
AA
BBB
AAA

输出样例 1

3

输入样例 2

5
A
ABA
BBB
ABABA
AAAAAB

输出样例 2

3

输入样例 3

6
A
B
A
B
A
B

输出样例 3

3

说明

第一个样例的解释：前缀和后缀可以重叠，因此子序列为 $A \to AA \to AAA$。

第三个样例的解释：子序列中的字符串允许相同，因此子序列可以是 $A \to A \to A$ 或 $B \to B \to B$。