Longest Word Formation

You are given a set of letters and a list of words. Your task is to find the longest word that can be formed using only the letters from the given set. Each letter in the given set can be used at most as many times as it appears. If there are multiple words with the maximum possible length, you should output the lexicographically smallest word among them.

In other words, let \(L\) be the string of available letters and \(W = [w_1, w_2, \ldots, w_n]\) be the list of words. A word \(w_i\) is valid if for each letter \(c\) in \(w_i\) we have:

[ \text{count}(c, w_i) \leq \text{count}(c, L) ]

Your goal is to pick the valid word with the maximum length, and if there are several, choose the one which is smallest in lexicographical order. If no word can be formed, output an empty string.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
letters_1
words_1
letters_2
words_2
... 
letters_T
words_T

Here, the first line contains an integer \(T\) (the number of test cases). For each test case, the first line contains a string \(letters\) consisting of available letters, and the second line contains a space-separated list of words.

outputFormat

For each test case, output on a separate line the longest word that can be formed using the given letters. If there is a tie, output the lexicographically smallest one. If no word can be formed, output an empty line.

## sample

4
abcdefg
abc def a ab bcd af
xyz
yxz yz y xx
a
aa a b
abcd
ab abc abcd d

abc
yxz
a
abcd

</p>