1108 : Finding Words

Description

Bob is writing his thesis, and he wants to use some advanced vocabulary. Unfortunately, he has forgotten how to spell some of the words. He just remember some characters at the beginning and ending. Now he need your help to find all the possible words.

Bob will give you a query which consists of lowercase letters and one asterisk(*), The asterisk could be replaced by zero or more letters. You need to find all the words which match the query. For example, if the query is “a*nd”, then you may tell him the words “and”, “append”, “attend”, etc.

Input

There is only one test case. The first line contains the number of words n(1 ≤ n ≤ 10⁵) in the dictionary. Each of the following n lines contains a word which consists of lowercase letters. The length of each word is not more than 30. The next line contains the number of queries q(1 ≤ q ≤ 10⁵). Each of the following q lines contains a query which consists of zero or more lowercase letters and one asterisk. The length of each query is not more than 30.

Output

For each query, print the number of words in the dictionary which match the query.

Sample

4
and
abandon
append
island
3
ab*
*nd
a*nd

1
3
2

Hint

Source

Author

Staginner