Pattern Occurrence Count

Given a text string \(S\) and \(n\) pattern strings \(T_1, T_2, \dots, T_n\), compute the number of times each pattern appears in \(S\). Note that occurrences may overlap. For example, if \(S = \texttt{abababa}\) and \(T_1 = \texttt{aba}\), then \(T_1\) appears 3 times in \(S\).

inputFormat

The input consists of the following:

• The first line contains the text string \(S\).
• The second line contains an integer \(n\), the number of patterns.
• Each of the following \(n\) lines contains a pattern string \(T_i\).

outputFormat

Output \(n\) lines, where the \(i\)-th line contains the number of times the pattern \(T_i\) appears in \(S\).

sample

abababa
2
aba
bab

3
2