A warehouse keeps a list of n shelf labels (a label may appear more than once; repeats are counted separately). You are then given q prefix queries. For each query prefix, report how many labels in the list have that prefix (a label counts if the query string is a prefix of it; a label is a prefix of itself).
All labels and prefixes consist of lowercase English letters only.
Input format
Line 1: an integer n.
Line 2: n space-separated labels.
Line 3: an integer q.
Line 4: q space-separated query prefixes.
Output format
Print q lines; line i is the number of labels having the i-th query as a prefix.
Constraints
- 1 <= n <= 100000
- 1 <= q <= 100000
- Each label/prefix has length 1..20, lowercase English letters.