Bob has a dictionary with N words in it. There are M operators. Each operator is one of two kinds.
1. Add a string to the dictionary. It is guaranteed that the string s was not added before.
2. For the given string s find the number of occurrences of the strings from the dictionary. If some string p from the dictionary has several occurrences in s you should count all of them.
The first line of the input gives the number of test cases T(T<=10); T test cases follow.
Each test case contains two integer N( 1≤N≤10^5) and M(1≤M≤10^5), The number of words in the dictionary initially, and the number of operators.
Next N line, each line has a string Wi, represents the ith word in the dictionary (0<|Wi|≤100000)
Next M line, each line contains integer t (1≤t≤2) and nonempty string s—the kind of the operator and the string to process. All strings consist of only lowercase English letters.
The sum of lengths of all strings in the input will not exceed 3*10^6.
For each operator of the second kind print the only integer c—the desired number of occurrences in the string s.
For each operator of the second kind print the only integer c—the desired number of occurrences in the string s.