Description

Word chain is a game similar to the idiom chain we often play. We are given a set of words and a starting letter, and we are asked to find the longest "dragon" that starts with this letter. Each word may appear at most twice in the "dragon".

When two consecutive words are connected, their overlapping part is merged into one. For example, beast and astonish become beastonish when chained. Moreover, the two adjacent parts must not have a containment relationship; for example, at and atide cannot be connected.

Input Format

The first line contains a single integer $n$, the number of words. Each of the next $n$ lines contains one word. The last line contains a single character, which is the starting letter of the "dragon". You can assume that a "dragon" starting with this letter always exists.

Output Format

Output only the length of the longest "dragon" that starts with this letter.

5
at
touch
cheat
choose
tact
a

23

Hint

Sample explanation: the resulting "dragon" is atoucheatactactouchoose.

Constraints: $n \le 20$.

Translated by ChatGPT 5