Substring Occurrence Count

Given a large string L and a list of smaller strings, count the number of times each smaller string appears in L as a substring. The counting should be non-overlapping. Formally, for a given substring (s) and string (L), count the number of indices (i) such that (L[i : i+|s|] = s), where after each match the search continues from the index (i+|s|).

inputFormat

The input is read from stdin and follows the format below:

• The first line contains an integer \(T\), the number of test cases.
• For each test case:
  • A line containing a non-empty string L (the large string).
  • A line containing an integer \(M\), the number of smaller strings.
  • \(M\) subsequent lines, each containing a non-empty smaller string.

outputFormat

For each test case, output one line containing (M) integers separated by a single space. Each integer corresponds to the count of occurrences of the given smaller string in L.## sample

1
ababcababc
3
ab
abc
c

4 2 2