Description

Given $n$ pattern strings $s_i$ and a text string $t$, count how many distinct pattern strings appear in the text. Two pattern strings are different if and only if their indices are different.

Input Format

The first line contains an integer $n$, the number of pattern strings.
Lines $2$ to $(n + 1)$ each contain one string; the string on line $(i + 1)$ is the pattern string $s_i$ with index $i$.
The last line contains a string, the text string $t$.

Output Format

Output a single integer on one line, which is the answer.

3
a
aa
aa
aaa

3

4
a
ab
ac
abc
abcd

3

2
a
aa
aa

2

Hint

Sample 1 Explanation

$s_2$ and $s_3$ have different indices, so each contributes once to the answer.

Sample 2 Explanation

$s_1$, $s_2$, and $s_4$ all appear in the string abcd.

Constraints

• For $10\%$ of the testdata, it is guaranteed that $n = 1$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^6$, $1 \leq |t| \leq 10^6$, $1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6$. $s_i, t$ contain only lowercase letters.

Translated by ChatGPT 5