You are given two strings ‘S’ and ‘T’. Your task is to find the minimum (Contiguous) substring ‘W’ of ‘S’, such that ‘T’ is a subsequence of ‘W’

A subsequence is a sequence that can be derived from another sequence by removing zero or more elements, without changing the order.

A substring is a contiguous part of a string.

For example:

For the given string “CodingNinjas”: “Ninja” is a substring while “dinas” is a subsequence. 

If there is no such Window in ‘S’ that covers all characters in ‘T’, return an empty string "". If there are multiple such minimum length windows, return the one with the smallest starting index.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows.

The first line of each test case contains the string ‘S’.
The second line of each test case contains the string ‘T’.

Output Format :

For each test case, print the substring of minimum length such that.

Output for each test case will be printed in a separate line.

Note :

  You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= S <= 1000      
1 <= T <= 100

Time limit: 1 sec