def verify_password(pair):

    pw=pair[0]
    hash=pair[1]

    chars = sorted(list(pw))

    for i in range(0,len(hash)-len(pw)+1):
        appoggio=[]

        if hash[i] in chars:

            for j in range(i,i+len(pw)):
                appoggio.append(hash[j])

            if sorted(appoggio)==chars:
                return True


    return False


T = int(input())
pairs = []
for _ in range(T):
    P = input()
    H = input()
    pairs.append((P, H))


for i in range(T):
    if(verify_password(pairs[i])):
        print("1")
    else:
        print("0")