You are given two strings A and B. You have to find smallest substring of A such that it contains all the letters of string B. The letters in both the strings can be any ASCII character.
Input constraints
1≤T≤1000
1≤|A|≤1000 where A denotes the length of the string A.
1≤|B|≤1000 where B denotes the length of the string B.
Input format
First line contains an integer, T,denoting the number of test cases.
First line in each test case contains a string, A.
Second line in each test case contains a string B.
Output format
Print the smallest substring of A such that it contains all the letters of string B. If there is no such substring, print 1. If there are multiple such substring, print the one which starts first. Answer for each test case should be in a new line.
The smallest substring that contains all the letter of string TisT is ThisIsAT which contains 8 letters.