题目描述

给定若干个单词和起始字母，用单词首尾重叠的方法拼接一条尽可能长的“龙”。相邻两个单词必须有非空的后缀、前缀相同，重叠部分只保留一份，且重叠长度必须严格小于这两个单词各自的长度，不能通过完全包含来拼接。每个输入单词最多使用两次，字母区分大小写。求以指定字母开头的最长长度。

输入格式

输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

样例

5
at
touch
cheat
choose
tact
a

23

数据范围

$1\le n\le20$，每个单词长度为 $1$ 至 $20$，只含大小写英文字母；保证至少有一个单词以指定字母开头。