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=\text{marisa}$, then you choose $\text{ad}$, the resulting string is $S=\text{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 \le n \le 1000$.
- $1 \le |T| \le 300$.
### Example
Input:
```
1
aa
aaaaa
```
Output:
```
5
```
