You are given two strings named str1 and str2 of length N and M respectively. Find whether string str2 contains one of the permutations of string str1 as its substring. In other words, whether there exists any permutation of string str1 that is a substring of str2.

For Example :

Input: str1 = “ab” , str2 = “aoba”
Output: True
Explanation : Permutations of first-string str1 i.e. “ab” are [ “ab”, “ba” ].
The substrings of str2 i.e. “aoba” are [ “a”, “o”, “b”, “a”, “ao”, “ob”, “ba”, “aob”, “oba”, “aoba” ].
The string “ba” is present in the list of substrings of string str2.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

The first and only line of each test case contains two single space-separated strings str1 and str2.

Output format :

 For each test case, print either “True” or “False”. 

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
1 <= M <= 10^4

Strings ‘str1’ and ‘str2’ consists only of lower case letters.

Time limit: 1 second