Count Words Starting with a Given Prefix

Count Words Starting with a Given Prefix

Given a trie of words, count how many words share a given prefix.

Input format

The first line contains N (distinct words, lowercase). The next N lines contain words. The next line contains Q. The next Q lines contain queries.

Output format

For each query, print the count of words starting with that prefix.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

1
nmmk
12
nmmk nm nm n nmm nmm qbzt lq z t i tibgj

1
1
1
1
1
1
0
0
0
0
0
0

2
qs pfw
8
qs qs q q e dh ur vawjb

1
1
1
1
0
0
0
0