题目描述

Adrian 很喜欢诗歌中的韵。他认为，两个单词押韵当且仅当它们的最长公共后缀的长度至少是其中较长单词的长度减一。也就是说，单词A 与单词B 押韵当且仅当 $\operatorname{LCS}(A,B) \ge \max(|A|,|B|)- 1$。（其中 $\operatorname{LCS}$ 是最长公共后缀 longest common suffix 的缩写）

现在，Adrian 得到了 $N$ 个单词。他想从中选出尽可能多的单词，要求它们能组成一个单词序列，使得单词序列中任何两个相邻单词是押韵的。

输入格式

第一行是一个整数 $N$。

接下来 $N$ 行，每行一个由小写英文字母组成的字符串，表示每个单词。所有单词互不相同。

输出格式

输出一行，为一个整数，表示最长单词序列的长度。

5
ask
psk
k
krafna
sk

4

提示

【样例解释】

一种最长单词序列是 ask-psk-sk-k。

【数据规模和约定】

$30\%$ 的测试数据：$1 \le N \le 20$，所有单词长度之和不超过 $3000$。

$100\%$ 的测试数据：$1 \le N \le 5 \times 10^5$，所有单词长度之和不超过 $3 \times 10^6$。