小 Adrian 是个押韵迷。他认为两个单词押韵当且仅当它们的最长公共后缀的长度与两个单词中较长者的长度相等，或者比较长者的长度少 1。换句话说，当且仅当 $LCS(A, B) \ge \max(|A|, |B|) - 1$ 时，单词 $A$ 和 $B$ 押韵。

一天，在阅读一本短篇小说集时，他决定构建一个尽可能长的单词序列，使得序列中任意两个相邻的单词都押韵。序列中的每个单词只能出现一次。

Adrian 已经对这个任务感到厌倦了，所以他决定回去继续看书，并请求你替他解决这个问题。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 500\,000$)。

接下来的 $N$ 行，每行包含一个由英文小写字母组成的单词。所有单词互不相同，且它们的总长度最多为 $3\,000\,000$。

输出格式

输出最长序列的长度。

子任务

在占总分 30% 的测试数据中，满足 $N \le 18$。

样例

输入样例 1

4
honi
toni
oni
ovi

输出样例 1

3

输入样例 2

5
ask
psk
krafna
sk
k

输出样例 2

4

输入样例 3

5
pas
kompas
stas
s
nemarime

输出样例 3

1

说明

第二个样例的解释： 唯一可能的序列是 ask-psk-sk-k。

第三个样例的解释： 没有任意两个单词押韵。