Ninja and the Game of Words

In this game, Ninja is provided with a string STR that might contain spaces, and a list or array WORDS consisting of N word strings. Ninja's task is to determine how many times each word in WORDS appears in STR.

Input:

The first line contains an integer T, representing the number of test cases.
The first line of each test case contains an integer N.
The second line contains the string STR.
The following N lines each contain a word from WORDS.

Output:

For each test case, output the frequency of each word in WORDS as it appears in STR. Print each result on a new line, maintaining the order given in WORDS.

Example:

Input:
 T = 1
 N = 3
 STR = "i am a Ninja"
 WORDS = ["Ninja","a","am"]

Output:
 [1,3,1]

Constraints:

• 1 <= T <= 100
• 1 <= |STR| <= 4000
• 1 <= N <= 4000
• 1 <= |WORDS[i]| <= 4000

Note:

The output must maintain the order of words as provided in WORDS. You don't have to print anything, just implement the function to return the answer.