A. BedWars Replay
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After another long BedWars session, Muzan and Honey decided to create a highlights video from their match.

They have $$$N$$$ recorded clips, each represented by a string of lowercase English letters.

First, Honey must arrange the clips in any order, using every clip exactly once, and concatenate them into one long replay $$$T$$$.

Before uploading it, Muzan suggests starting the replay from a different moment. For an integer $$$k$$$ with $$$0 \le k \lt |T|$$$, a cyclic shift by $$$k$$$ characters moves the first $$$k$$$ characters of $$$T$$$ to the end. They may choose any such $$$k$$$ to obtain a new replay $$$T'$$$.

For example, if $$$T = \texttt{abcde}$$$, its possible cyclic shifts are:

abcde bcdea cdeab deabc eabcd

They are looking for a famous BedWars combo, represented by the string $$$P$$$.

Choose both the order of the clips and the cyclic shift so that the number of linear occurrences of $$$P$$$ as a substring of $$$T'$$$ is maximized. Occurrences are allowed to overlap.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 12$$$), the number of clips.

Each of the next $$$N$$$ lines contains a nonempty string $$$S_i$$$ ($$$1 \le |S_i| \le 50$$$).

The last line contains a nonempty string $$$P$$$ ($$$1 \le |P| \le 50$$$).

All strings contain only lowercase English letters.

Output

Print one integer, the maximum possible number of occurrences of $$$P$$$ after choosing the order of the clips and the cyclic shift.

Example
Input
2
baa
b
abba
Output
1
Note

The clips are $$$\texttt{baa}$$$ and $$$\texttt{b}$$$. The two possible concatenations are $$$\texttt{baab}$$$ and $$$\texttt{bbaa}$$$, and neither contains $$$\texttt{abba}$$$.

Rotating $$$\texttt{baab}$$$ by two characters gives $$$\texttt{abba}$$$, which contains the target exactly once. Therefore, the answer is $$$1$$$.