你想给你的朋友写一首非常特别的诗。你已知一个包含 $n$ 个你朋友喜欢的单词的列表。我们称这些单词为“美丽单词”。你希望你诗歌的每一行都以一个美丽单词开头和结尾。对于任意给定的一行，其开头和结尾必须使用同一个美丽单词，但不同的行可以使用不同的美丽单词。你不需要关心每行中间的其他单词（只需要关心第一个和最后一个单词！）。

每当某一行第一个单词的某个前缀与前一行最后一个单词的某个后缀相匹配时，你的朋友就会觉得你的诗很美。此外，如果你的朋友在连续的两行中看到了相同的美丽单词，或者某一行的第一个单词与前一行的最后一个单词没有共同的前缀/后缀（即最长公共前缀/后缀长度为 $0$），他们会很讨厌。因此，你需要确保你的诗中不会出现这样的情况。

更具体地说，你可以将第 $i$ 行（$i \ge 2$）的“莎士比亚指数”（Shakespearian index）定义为：第 $i$ 行第一个单词的最长前缀，且该前缀同时也是第 $i - 1$ 行最后一个单词的后缀的长度。第一行的莎士比亚指数始终为 $0$。诗歌的美丽度定义为诗歌中所有行的莎士比亚指数之和。

你能写出的最美丽的诗歌的美丽度是多少？

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 500$）。

接下来的 $n$ 行，每行包含一个不同的美丽字符串，这是一个仅包含英文小写字母 a-z 的单词。每个美丽字符串的长度最多为 $2000$。

输出格式

输出一个整数，表示你能写出的最美丽诗歌的美丽度。如果你可以写出一首无限美丽的诗歌，请输出 Shakespeare, who?。

样例

样例输入 1

3
raccoon
elephant
anteater

样例输出 1

4

样例说明 1

对于第一个样例，一种可能的最美诗歌（忽略标点符号）为： elephant, oh mighty elephant, anteater, oh hungry anteater, raccoon, oh poor raccoon!

样例输入 2

2
tractor
torrent

样例输出 2

Shakespeare, who?