Count Occurrences of Substrings

You are given a string S and Q queries. Each query consists of a substring. Your task is to determine the number of occurrences of each query substring in the string S. Note that occurrences may overlap. For example, when S = "aaaa" and the query substring is "aa", the answer is 3 because the substring appears at indices 0, 1, and 2.

The problem can be defined mathematically as follows: For a given substring p and string S, count the number of indices i such that

[ S[i \ldots i+|p|-1] = p ]

Input will be read from standard input (stdin) and the result for each query should be printed to standard output (stdout), each on a separate line.

inputFormat

The first line contains the string S.

The second line contains an integer Q representing the number of queries.

The following Q lines each contain a non-empty substring that is a query.

outputFormat

For each query, output an integer on a new line representing the number of occurrences of the query substring in S.

## sample

abcd
2
a
bc

1
1

</p>