Shuffle Hashing
Polycarp has built his own web service. Being a modern web service it includes login feature. And that always implies password security problems.Polycarp decided to store the hash of the password, generated by the following algorithm:  take the password $$$p$$$, consisting of lowercase Latin letters, and shuffle the letters randomly in it to obtain $$$p'$$$ ($$$p'$$$ can still be equal to $$$p$$$);  generate two random strings, consisting of lowercase Latin letters, $$$s_1$$$ and $$$s_2$$$ (any of these strings can be empty);  the resulting hash $$$h = s_1 + p' + s_2$$$, where addition is string concatenation. For example, let the password $$$p =$$$ "abacaba". Then $$$p'$$$ can be equal to "aabcaab". Random strings $$$s1 =$$$ "zyx" and $$$s2 =$$$ "kjh". Then $$$h =$$$ "zyxaabcaabkjh".Note that no letters could be deleted or added to $$$p$$$ to obtain $$$p'$$$, only the order could be changed.Now Polycarp asks you to help him to implement the password check module. Given the password $$$p$$$ and the hash $$$h$$$, check that $$$h$$$ can be the hash for the password $$$p$$$.Your program should answer $$$t$$$ independent test cases.
The first test case is explained in the statement.In the second test case both $$$s_1$$$ and $$$s_2$$$ are empty and $$$p'=$$$ "threetwoone" is $$$p$$$ shuffled.In the third test case the hash could not be obtained from the password.In the fourth test case $$$s_1=$$$ "n", $$$s_2$$$ is empty and $$$p'=$$$ "one" is $$$p$$$ shuffled (even thought it stayed the same). In the fifth test case the hash could not be obtained from the password.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.The first line of each test case contains a non-empty string $$$p$$$, consisting of lowercase Latin letters. The length of $$$p$$$ does not exceed $$$100$$$.The second line of each test case contains a non-empty string $$$h$$$, consisting of lowercase Latin letters. The length of $$$h$$$ does not exceed $$$100$$$.
For each test case print the answer to it — "YES" if the given hash $$$h$$$ could be obtained from the given password $$$p$$$ or "NO" otherwise.
inp = int(input())
for _ in range(inp):
    p = input()
    h = input()
    ans = 0
    n = len(p)
    m = len(h)
    if n > m:
        print('NO')
        continue
    lis = sorted(p)
    for i in range(m - n + 1):
        s = sorted(h[i:i + n])
        if s == lis:
            ans = 1
            break
    if ans == 1:
        print('YES')
    else:
        print('NO')
t = int(input())
for i in range(t):
    d = dict()
    p = input()
    h = input()
    n = len(p)

    def find_possible(d, p, h, n):
        if len(h) < n:
            print('NO')
            return
        for i in p:
            if i not in d:
                d[i] = 0
            else:
                d[i] += 1
        for ind in range(len(h) - len(p) + 1):
            new = dict()
            for val in h[ind:ind + n]:
                if val not in new:
                    new[val] = 0
                else:
                    new[val] += 1
            if new == d:
                print('YES')
                return
        print('NO')
    find_possible(d, p, h, n)
n = int(input())
result = []
for i in range(n):
    p = list(input())
    p.sort()
    hash = list(input())
    a = True
    for i in range(len(hash) - len(p) + 1):
        if sorted(hash[i:len(p) + i]) == p:
            result.append('YES')
            a = False
            break
    if a:
        result.append('NO')
for i in result:
    print(i)