题目描述

字母链拼接是一个文字游戏。给定一组单词和一个开头字母，要求以该字母开头，将单词首尾拼接成一条尽可能长的「链」。

拼接规则如下：

• 每个单词最多使用两次。
• 相邻两个单词的重合部分合为一部分，例如 beast 和 astonish 可拼成 beastonish。
• 相邻两部分不能存在包含关系，例如 at 和 atide 不能相连（at 是 atide 的前缀）。

请计算以给定字母开头的最长链的长度。

输入格式

第一行一个整数 $n$，表示单词数。

接下来 $n$ 行，每行一个单词。

最后一行一个字符，表示链的开头字母。保证以此字母开头的链一定存在。

输出格式

一行一个整数，表示最长链的长度。

样例

5
at
touch
cheat
choose
tact
a

23

提示

样例解释

拼成的链为 atoucheatactactouchoose，长度为 23。

数据范围

$n \le 20$。