
If the dictionary is: {"cat", "rat", "bat", "hat"}
And query words are "?at" and "b?t", then:
"?at" => can be matched by all the 4 dictionary words by replacing '?' with 'c', 'r', 'b' or 'h'.
"b?t" => can only be matched by the dictionary word "bat" by replacing '?' with 'a'.
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains two integers ‘N’ and ‘L’, where N denotes the number of words in the dictionary and L denotes the length of words in the dictionary and queries.
The next line contains N words each of size L, denoting the words in the dictionary.
The next line contains a single integer ‘Q’ denoting the number of queries.
The following Q lines, each contains a word ‘W’ of size L, denoting the query word.
For each test case print Q integers in a separate line, each denoting the number of dictionary words that can be matched by the query word.
Output for each test case will be printed in a separate line.
You are not required to print anything; it has already been taken care of. Just implement the function.
1 <= T <= 10
1 <= N <= 100
1 <= L <= 7
1 <= Q <= 100
1 <= word.size <= L
Time limit: 1 sec
2
5 3
cat
map
bat
man
pen
4
?at
ma?
?a?
??n
1 5
aaaaa
1
bbbbb
2
2
4
2
0
For test case 1 :
Query1: “?at” matches with “cat” and “bat”
Query2: “ma?” matches with “map” and “man”
Query3: “?a?” matches with “cat”, “bat”, “map” and “man”
Query4: “??n” matches with “man” and “pen”
For test case 2 :
Query1: “bbbbb” doesn’t matches with any dictionary words
2
5 3
cat
map
bat
man
pen
4
cat
ma?
?a?
pen
2 5
aaaaa
bbbbb
1
bbbbb
1
2
4
1
1