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
Examples
Example 1
Inputwords = ["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".