Description

Word Dragon is a game similar to the idiom chain game we often play. Now we are given a set of words and a starting letter, and we need to find the longest possible "dragon" (each word can appear at most twice in the "dragon") that begins with this letter. When two words are connected, their overlapping parts merge into one. For example, "beast" and "astonish" would combine into "beastonish." Additionally, adjacent parts cannot have an inclusion relationship. For instance, "at" and "atide" cannot be connected.

Input Format

The first line of input is a single integer n (n ≤ 20) representing the number of words. The following n lines each contain one word (consisting of uppercase or lowercase letters, with a maximum length of 20). The last line of input is a single character, representing the starting letter of the "dragon." You may assume that a "dragon" starting with this letter definitely exists.

Output Format

Simply output the length of the longest "dragon" that starts with the given letter.

5
at
touch
cheat
choose
tact
a

23