Words Magic with Prefix Replacement Problem

Ninja is provided with a dictionary of words, WORDS, and a sentence, SENTENCE, which consists of words separated by spaces. The goal is to minimize the size of the SENTENCE by replacing its words using the following rule:

Ninja can replace a word from the SENTENCE with a word from WORDS if and only if a prefix of that word exists in WORDS. If multiple replacements are possible, choose the smallest word among them.

Example of Prefixes:

For the string ‘abcd’, the prefixes are: "a", "ab", "abc", "abcd".

Input:

The first line contains an integer ‘T’, the number of test cases.
Each test case consists of:
- First line with integer ‘N’, the number of words in WORDS.
- Second line with ‘N’ space-separated words.
- Third line with a string, the SENTENCE.

Output:

For each test case, output the minimized SENTENCE based on the replacement rule on a new line.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 100
• Each word in WORDS consists of lowercase letters only.
• 1 <= |SENTENCE| <= 100000
• The SENTENCE has no leading or trailing spaces.

Note:

You do not need to print the output explicitly; the function itself handles outputting results.