小Adrian是押韵的粉丝。他认为，如果两个单词押韵当且仅当它们最长的共同后缀的长度不小于其中两个单词长度最长的那个长度减1。换句话说，A和B押韵当且仅当它是LCS（A，B）≥max（|A|，| B |）−1（|A|，|B|分别表示两个单词的长度）。
有一天，他在读短篇小说集时，决定创作最长的这样押韵的一系列词。序列中相邻的两个词押韵并且每个单词只出现一次。Adrian已经厌倦了这个任务，所以他决定去读小说，并要求你解决这个任务，而不是他。
输入：
第一行一个整数N（1<=N<=500000）。
接下来每一行一个小写英文单词，每一次单词都是不同的，所有单词的的总长度不超多3000000。
输出：
输出这样的押韵序列最长的那个序列的长度（即总共单词个数）。
评分：
30%的数据，N<=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