Prefix Count

Given a dictionary, containing a list of words, and a list of queries, which consists of a list of prefixes, compute the result of each query. Each query is simply a string denoting a prefix. For each query, return the number of words in the dictionary that contain that prefix.

There may be duplicate words in the dictionary. In a query, you should account for all the duplicate words.

Only lowercase English letters will be used.

Constraints

1 <= words.length <= 100001

1 <= words[i].length <= 10

Examples

Example 1:

Input: words = ["forgot", "for", "algomonster", "while"], prefixes = ["fo", "forg", "algo"]

Output: [2, 1, 1]

Explanation:

"forgot" and "for" have the prefix "fo". Only "forgot" has "forg", and only "algomonster" has the prefix "algo".