题目描述

有一个王朝，他们国王的名字用姓氏的简写来标记每一代。为了保证王朝的稳定，现在这个王朝的继承人的名字需要满足继承者名字的第一个字母要和前代名字最后一个字母相同。然后拼接起来的名字，第一个字母和最后一个字母相同。现在有一个考古博士，知道了这个王朝国王和亲戚的名字。问你这个王朝所能够得到的最长字符串。

输入

第一行一个整数n(1≤n≤5·1e5),接下来n行，每行一个非空字符串，全由小写字母组成，字符串长度不超过10

输出

最长满足要求的长度，如果没有输出0

构成的字符串必须按输入顺序首尾相接，不能乱序拼接。

样例 #1

样例输入 #1

3
abc
ca
cba

样例输出 #1

6

样例 #2

样例输入 #2

4
vvp
vvp
dam
vvp

样例输出 #2

0

样例 #3

样例输入 #3

3
ab
c
def

样例输出 #3

1

提示

在第一个样本中，可以存在两个王朝：一个叫做 "abcca"（第一和第二个国王），另一个叫做 "abccba"（第一和第三个国王）。

第二个样本中没有可接受的王朝。

第三个样本中唯一的王朝只有一个国王，他的名字是 "c"。