Jong Hyok and String

Problem Description

Jong Hyok loves strings. One day he gives a problem to his friend you. He writes down n strings Pi in front of you, and asks m questions. For i-th question, there is a string Qi. We called strange set(s) = {(i, j) | s occurs in Pi and j is the position of its last character in the current occurence}. And for ith question, you must answer the number of different strings t which satisfies strange set(Qi) = strange set(t) and t is a substring of at least one of the given n strings.

Input

First line contains T, a number of test cases. For each test cases, there two numbers n, m and then there are n strings Pi and m strings Qj.(i = 1…n, j = 1…m) 1 <= T <= 10 1 <= n <= 100000 1 <= m<= 500000 1 <=|Pi|<=100000 1 <=|Qi|<=100000 $\sum_{i=1}^{n} |P_i|\leq 100000$ File size is less than 3.5 megabytes.

Output

For each test case, first line contains a line “Case #x:”, x is the number of the case. For each question, you should print one integer in one line.

Sample Input

1
2 2
aba
ab
a
ab

Sample Output

Case #1:
1
2

Hint

strange set(“a”) ={(1, 1), (1, 3), (2, 1)}. strange set(“ab”) ={(1, 2), (2, 2)}. strange set(“b”) ={(1, 2), (2, 2)}.

Author

金策工业综合大学（DPRK）

Source

2016 Multi-University Training Contest 9