Most Frequent Keyword

You are given a message and a list of keywords. Your task is to find the most frequent keyword that appears in the message. The message should be processed by converting all letters to lower-case and removing all punctuation. In the case of a tie, choose the lexicographically smallest keyword. If none of the keywords is found in the processed message, output None.

Specifically, for each test case, you will be given the number of keywords K, a list of K keywords, and a message string. Remove punctuation from the message and convert it to lower-case. Then count the frequency of each keyword. The keyword with the highest frequency is the answer. If two or more keywords share the frequency, the one that comes first in lexicographical order is chosen. If no keyword appears in the message, output "None".

Note: The frequency of a keyword k is given by:

[ \text{frequency}(k) = \sum_{i=1}^{n} \delta (w_i, k), ]

where \(w_1, w_2, \ldots, w_n\) are the words in the processed message and \(\delta (w, k)=1\) if \(w=k\) and 0 otherwise.

inputFormat

The input is given from standard input (stdin). The first line contains an integer T indicating the number of test cases. For each test case:

• The first line contains an integer K, the number of keywords.
• If K > 0, the next line contains K space-separated keywords. If K = 0, this line will be empty.
• The following line contains the message string.

Process each test case independently.

outputFormat

For each test case, output the most frequent keyword on a new line. If no keyword is found in the message, output None.

## sample

1
3
word sample test
This is a test message with the word test appearing twice.

test