Given a string and a set of patterns, determine for each pattern the number of positions at which it occurs in the string.
The first line contains a string of length n~(1 \le n \le 10^5).
The second line contains an integer k~(1 \le k \le 5 \cdot 10^5) — the number of patterns. Each of the next lines contains one pattern. The total length of all patterns does not exceed 5 \cdot 10^5.
The string and the patterns consist of lowercase Latin letters '' - ''.
For each pattern, print on a separate line the number of its occurrences in the string.
Example 1