Prefix Count Queries

You are given \(N\) strings \(S_1, S_2, \dots, S_N\). Then, you are given \(M\) queries. For each query a string \(T\) is provided, and your task is to count how many strings among \(S_1, S_2, \dots, S_N\) are prefixes of \(T\). A string \(S\) is called a prefix of \(T\) if \(T\) starts with \(S\). Note that a string is considered a prefix of itself.

Input Constraints:

• The total length of all strings (both the \(N\) input strings and the \(M\) query strings) does not exceed \(10^6\).
• All strings consist of lowercase English letters only.

inputFormat

The first line contains an integer \(N\) representing the number of strings.

The following \(N\) lines each contain one non-empty string \(S_i\).

The next line contains an integer \(M\) representing the number of queries.

The following \(M\) lines each contain one non-empty query string \(T\).

outputFormat

For each query, output a single line containing the count of strings among \(S_1, S_2, \dots, S_N\) that are prefixes of the query string \(T\).

sample

3
a
ab
abc
3
a
ab
abc

1
2
3