题目描述

小z最近又迷上了一款经典游戏之，<<成语接龙>> 现给定 $n$ 个仅包含小写字母的字符串 $S_i$ ， 当存在两个字符串 $S_i$ 和 $S_j$ ,并且符合以下两个条件时，可以前后拼接

• $i<j$
• $S_i$ 末尾字母与 $S_j$ 的开头字母相同时，$S_j$ 可以连接在 $S_i$ 的后面

例如：s[1]="abc" ,s[2]="cxz" 可以拼接为"abccxz" 问从$n$个字符串中选取若干个，按照如上规则拼接时或者不选择拼接，字符串最后首尾字母相同的情况下，长度最大是多少？

输入格式

第一行一个整数 $n$ ,代表给定 $n$ 个字符串

接下来 $n$ 行 ，每行一个字符串 ，字符串长度不大于20

n<=1e4

输出格式

按照规则拼接字符串的最大长度

5

abc

ccde

cde

cccccccccz

ea

9

提示

s[1]: abc

s[2]: ccde

s[5]: ea

按规则，前后顺序可拼接成 "abcccdeea" 最后拼接结果首尾字母相同(a)

测试数据2：

1

abcdexyz

输出 0

测试数据3：

1

q

输出 1