You are given n strings. Your task is to construct a new string S by following these steps:
- Start with an empty string S.
- In each move, choose a string from the given n strings and append it to the end of S. You can choose a string multiple times.
- From the second move, the chosen string must have its first character equal to the last character of the previously chosen string. And that first character is removed. For example, S=marisa, then you choose ad, the resulting string is S=marisad.
You need to find the smallest possible length of S that contains a target string T as a subsequence.
### Input
- The first line contains an integer n.
- The next n lines, each line contains a string, their lengths do not exceed 10.
- The last line contains string T.
### Output
- Print an integer, the minimum length of S.
### Constraints
- 1≤n≤1000.
- 1≤|T|≤300.
### Example
Input:
1aaaaaaa
Output:
5
