Given a string and patterns, count for each pattern the number of positions where it appears in the string.

The first input line has a string of length $n$ .

The next input line has an integer $k$ : the number of patterns. Finally, there are $k$ lines that describe the patterns.

The string and the patterns consist of characters a–z.

• $1 \le n \le 10^5$
• $1 \le k \le 5 \cdot 10^5$
• the total length of the patterns is at most $5 \cdot 10^5$

For each pattern, print the number of positions.