Substring search P79329

You are given a string $s$ and many short patterns, all of the same length. The string $s$ and the patterns are composed only of ‘a’ and ‘b’ characters. For every given pattern, you must tell how many times it is included in $s$. Can you do it efficiently, both in time and in space?

Input

Input starts with a number $t$, followed by $t$ cases. Each case begins with a non-empty string $s$, followed by a number $p \ge 1$, followed by $p$ non-empty patterns. The only characters in $s$ and in the patterns are ‘a’ and ‘b’. The length of $s$ is at most $10^6$. All the patterns of the same case have the same length, which is at most 60. No given pattern is longer than $s$.

Output

For every case, print the case number starting at 1 followed by the number of times that each given pattern is included in $s$. Print a blank line after every case.