Jong Hyok and String

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.

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.

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.

1
2 2
aba
ab
a
ab

Case #1:
1
2

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

金策工业综合大学（DPRK）

2016 Multi-University Training Contest 9