Poetry with an Asterisk

Interview

Time limit5sMemory limit128 MB

Summary

Count for each one-asterisk query how many dictionary words start with its prefix and end with its suffix without overlap.

Level: Medium5 of 10
Topics: Hash map, String
Solved: No attempts yet

Problem

In a certain exotic language there are $N$ distinct non-empty words made of lowercase English letters.

The language has a peculiar property found in no other language: in writing it uses a special sign, the asterisk (*), which can replace any (possibly empty) contiguous fragment of a single word. This makes written words ambiguous, which lets the language express unusually deep poems. It complicates everyday life, but in the end art matters more than biography.

You are given the list of all words in the language (in full, without asterisks) and the text of a poem in which every word contains exactly one asterisk. Compute how many words of the language match each word of the poem.

Formally, a poem word consists of a prefix $P$ , then the asterisk, then a suffix $S$ (either part may be empty). It matches a language word $W$ exactly when $W$ starts with $P$ , ends with $S$ , and $|W| \ge |P| + |S|$ (so the fragment hidden by the asterisk is a valid contiguous piece).

For example, if the language contains the words zupa, z, malpy, intruz, pyszny, then in the poem z*, m*y, g*ingo the first poem word is matched by two language words, the second by one, and the third by none (there must have been a misprint).

Input

The first line contains a natural number $Z$ ( $1 \le Z \le 10$ ), the number of test sets. The test sets follow.

The first line of each test set contains a natural number $N$ ( $1 \le N \le 100000$ ), the number of words in the language.

Each of the next $N$ lines contains one word of the language. The words are pairwise distinct, and each consists of 1 to 10 lowercase English letters.

The next line contains a natural number $K$ ( $1 \le K \le 100000$ ), the number of words in the poem.

Each of the next $K$ lines contains one word of the poem. These words need not be distinct; each consists of 1 to 10 characters, exactly one of which is an asterisk and the rest lowercase English letters.

Output

For each test set, print $K$ lines. The $i$ -th of those lines contains the number of language words that match the $i$ -th word of the poem.

Examples3

Example 1

Input

1
5
zupa
z
malpy
intruz
pyszny
3
z*
m*y
g*ingo

Expected output

2
1
0

Example 2

Input

1
3
a
bb
ccc
5
*
a*
*c
b*b
c*c

Expected output

Example 3

Input

1
3
a
aa
aaa
6
a*a
a*
*a
a*aa
aa*a
aaa*a

Expected output