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 ≥ 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⁶. 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.