1955D - Inaccurate Subsequence Search - CodeForces Solution

t = int(input())

bEle = [None for _ in range(10**6+1)]
for _ in range(t):
    n,m,k = map(int,input().split())

    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    for i in range(m):
        if bEle[b[i]]==None:
            bEle[b[i]] = 1
        else:
            bEle[b[i]] += 1
    
    count = 0
    ans = 0
    for i in range(m):
        if bEle[a[i]]!=None:
            bEle[a[i]] -=1
            if bEle[a[i]]>=0:
                count+=1
    
    if count>=k:
        ans+=1
        for i in range(m,n):
        if bEle[a[i-m]]!=None:
            bEle[a[i-m]] += 1
            if bEle[a[i-m]]>0:
                count-=1
        if bEle[a[i]]!=None:
            bEle[a[i]]-=1
            if bEle[a[i]]>=0:
                count+=1
        if count>=k:
            ans+=1
    
    for i in range(m):
        bEle[b[i]] = None
    
    print(ans)