Given a string S and a string T, find the minimum substring in S which will contain all the characters in T.

For example,

S = "ADOBECODEBANC"

T = "ABC"

Minimum substring is "BANC".

The first line contains the number of test cases C. C test cases follow. Each case contains string S on the first line, String T on the second line.

1 <= T <= 100 

1 <= string length <= 1000 

Output C lines, one for each test case, containing the minimum substring.

If there is no such substring in S that covers all characters in T, return the string "$".

If there are multiple such substring, output the leftmost one.