Counting Substring Occurrences

In this problem, you are given a string ( s ) and a list of query strings. For each query, you are required to count the number of times that the query string appears in ( s ) as a substring. Note that the occurrences may overlap. For example, if ( s = \text{ababa} ) and the query is ( \text{aba} ), the answer is 2.

inputFormat

The input is provided via standard input and consists of multiple lines. The first line contains the string ( s ). The second line contains an integer ( n ), representing the number of queries. Each of the following ( n ) lines contains one query string.

outputFormat

Output a single line with ( n ) integers separated by spaces. Each integer corresponds to the number of times the respective query appears in ( s ) as a substring.## sample

ababa
1
aba

2