This content is archived!For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.
You have been hired by a dating site to code their incredibly advanced matching algorithm. The site has found that the best indicator of a good couple is how many letters their names share: the more the better!
Kate share two letters: they are an okay match.
Johnina, on the other hand, share four letters: they are a great match! Given a person and a list of potential partners, find the best match.
The first line of the input provides the number of test cases, T (1 \leq T \leq 100). T test cases follow. Each test case begins with a string S, a person’s name, and N (1 \leq N \leq 1000), the number of potential partners. N lines follow, each containing one name. The names will appear in alphabetical order and will be entirely capitalized.
For each test case, output the name of the best partner. If multiple partners share the same number of letters with the person, output the name which comes first alphabetically.
Explanation for Sample Output
In the first test case, Sarah shares three letters (
a) with Aaron, three (
h) with Ashley, and five letters with Sahar, so Sahar is the best match.
In the second test case, Meagan shares three letters (
n) with Andrew, two (
n) with Ann, and three (
n) with Jane. Since Andrew’s name comes first alphabetically, he’s chosen as the best match.