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^{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.

Public test cases

**Input**

2 aabaaaabaaab 3 aaba aaaa baab bbbbbbbb 1 bb

**Output**

Case 1: 2 1 0 Case 2: 7

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++