1648 - 第四届“恒生杯”程序设计大赛决赛 F

Time Limit: 1s Memory Limit: 256MB

Submissions: 27 Solved: 7
Description

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".

Input

 

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

 

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

Sample Input

    
Sample Output

    
Hint

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.

Source