Server Time: Tue Jul 23, 2019 12:28 am
Welcome ( logout
1427 - Substring Frequency (II)
  PDF (English) Statistics Forum
Time Limit: 5 second(s) Memory Limit: 128 MB

A string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given a string T and n queries each with a string Pi, where the strings contain lower case English alphabets only. You have to find the number of times Pi occurs as a substring of T.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 500). The next line contains the string T (1 ≤ |T| ≤ 106). Each of the next n lines contains a string Pi (1 ≤ |Pi| ≤ 500).

Output

For each case, print the case number in a single line first. Then for each string Pi, report the number of times it occurs as a substring of T in a single line.

Sample Input

Output for Sample Input

2

5

ababacbabc

aba

ba

ac

a

abc

3

lightoj

oj

light

lit

Case 1:

2

3

1

4

1

Case 2:

1

1

0

Notes

1.      Dataset is huge, use faster I/O methods.

2.       If S is a string then |S| denotes the length of S.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan