Problem B
Nicknames

You and your group of friends often use nicknames to refer to each other. One day, you noticed that some of the nicknames could refer to more than one person, which causes confusion. For example, jo could refer to either john or joseph. Your task is to determine how many names can be matched with a given nickname.

A name and a nickname are said to match if and only if the nickname is a prefix of the name. In other words, given a name $N$ of length $l_ N$ and a nickname $K$ of length $l_ K$, $N$ and $K$ match iff:

1. $l_ N \geq l_ K$.

2. $N[0] = K[0]$ , $N[1] = K[1],\; \ldots \; ,N[l_ K-1] = K[l_ K-1]$.

You will be given a list of $A$ names and $B$ nicknames. For each nickname, print the number of names that match with it.

Input

The first line contains an integer, $1 \le A \le 100\, 000$, the number of names.

The next $A$ lines contain the names, each name on one line. Each name is between $1$ and $10$ characters long and consists of lowercase letters only. All names are unique.

The next line contains an integer, $1 \le B \le 100\, 000$, the number of nicknames.

The next $B$ lines contain the nicknames, each nickname on one line. Each nickname is between $1$ and $10$ characters long and consists of lowercase letters only.

Output

For each nickname, print the number of names that it matches with. Output each integer on a separate line, in the same order as the input.

Subtasks

1. ($40$ Points): $A,B \le 1\, 000$. All nicknames are exactly $1$ character long.

2. ($30$ Points): $A,B \le 100\, 000$. All nicknames are exactly $1$ character long.

3. ($30$ Points): No additional constraint.

Note: Sample Input $3$ corresponds to Subtask $3$. You can ignore it if you are only attempting Subtask $1$ or $2$.

Warning

The input files are large. Please use fast I/O methods.

3
j
jason
susan
3
j
s
x

2
1
0

10
a
ba
cba
dcba
edcba
fedcba
gfedcba
hgfedcba
ihgfedcba
jihgfedcba
9
a
b
c
d
e
f
g
h
i

1
1
1
1
1
1
1
1
1

4
string
substring
substrate
submarine
4
string
substr
sub
ring

1
2
3
0