Description

You are given a text string $S$ and $n$ pattern strings $T_{1 \sim n}$. Please find, for each pattern string $T_i$, the number of times it appears in $S$.

Input Format

The first line contains a positive integer $n$, representing the number of pattern strings.

The next $n$ lines each contain a non-empty string $T_i$ consisting of lowercase English letters, where the $i$-th line corresponds to $T_i$.

The last line contains a non-empty string $S$ consisting of lowercase English letters.

The testdata does not guarantee that any two pattern strings are different.

Output Format

Output $n$ lines. The $i$-th line contains a non-negative integer, representing the number of times $T_i$ appears in $S$.

5
a
bb
aa
abaa
abaaa
abaaabaa

6
0
3
2
1

Hint

For $100\%$ of the data, $1 \le n \le 2 \times {10}^5$, the total length of $T_{1 \sim n}$ is at most $2 \times {10}^5$, and the length of $S$ is at most $2 \times {10}^6$.

Translated by ChatGPT 5