T = int(input())
def func(s):
    s1,s2,s3,K = s.strip().split()
    K = int(K)
    count=0
    while(s3):
        i=0
        if s1 and s1[0]==s3[0]:
            count+=1
            while(s1 and s1[0]==s3[0]):
                s1 = s1[1:]
                s3 = s3[1:]
        elif s2 and s2[0]==s3[0]:
            count+=1
            while(s2 and s2[0]==s3[0]):
                s2 = s2[1:]
                s3 = s3[1:]
        else:
            return 0
    if count<=K:
        return 1
    return 0
result = []
for i in range(T):
    s = input()
    result.append(func(s))
for j in result:
    print(j)