5.2 🥔🫑 Good Vegetable Sets 🥕🍅

Score: 20pts

Time Limit: 5.00 sec

Alice is an urban gardener who loves growing a variety of vegetables in her small backyard. She has a garden bed where she plans to plant a set of vegetables represented by the array a of length n.

Alice also has a set of m specific vegetables she wants to grow, represented by the array b. She considers a subset of m vegetables from her garden bed to be a "good" set if they can be rearranged to match at least k of the vegetables in b.

For example, if b = [1, 2, 3, 4] and k = 3, then the vegetable sets [4, 1, 2, 3] and [2, 3, 4, 5] are good (they can be rearranged to match 3 or more vegetables in b), while [3, 4, 5, 6] and [3, 4, 3, 4] are not good.

Alice wants to count how many contiguous subsets of length m in her garden bed a will be considered good sets. In other words, she wants to find the number of positions 1 ≤ l ≤ n-m+1 such that the vegetables a[l], a[l+1], ..., a[l+m-1] form a good set.

Can you help Alice solve this problem?

Alice also has a set of m specific vegetables she wants to grow, represented by the array b. She considers a subset of m vegetables from her garden bed to be a "good" set if they can be rearranged to match at least k of the vegetables in b.

For example, if b = [1, 2, 3, 4] and k = 3, then the vegetable sets [4, 1, 2, 3] and [2, 3, 4, 5] are good (they can be rearranged to match 3 or more vegetables in b), while [3, 4, 5, 6] and [3, 4, 3, 4] are not good.

Alice wants to count how many contiguous subsets of length m in her garden bed a will be considered good sets. In other words, she wants to find the number of positions 1 ≤ l ≤ n-m+1 such that the vegetables a[l], a[l+1], ..., a[l+m-1] form a good set.

Can you help Alice solve this problem?

Constraints

t(1≤t≤10^4)

n,m, and k(1≤k≤m≤n≤2*10^5)

a1,a2,…,an (1≤ai≤10^6)

b1,b2,…,bn (1≤ai≤10^6)

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5 .Similarly, the sum of m over all test cases does not exceed 2*10^5.

n,m, and k(1≤k≤m≤n≤2*10^5)

a1,a2,…,an (1≤ai≤10^6)

b1,b2,…,bn (1≤ai≤10^6)

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5 .Similarly, the sum of m over all test cases does not exceed 2*10^5.

Input Format

The first line contains an integer t — the number of test cases.

The first line of each test case contains three integers

n,m,k— the number of elements in arrays a and b, the required number of matching elements.

The second line of every test case contains n integers a1,a2,a3….an - the elements of array a

The third line of every test case contains m integers b1,b2,b3….bn - the elements of array b

The first line of each test case contains three integers

n,m,k— the number of elements in arrays a and b, the required number of matching elements.

The second line of every test case contains n integers a1,a2,a3….an - the elements of array a

The third line of every test case contains m integers b1,b2,b3….bn - the elements of array b

Output Format

For each test case, output the number of good subsegments of array a on a separate line.

Example 1

Input:

5

7 4 2

4 1 2 3 4 5 6

1 2 3 4

7 4 3

4 1 2 3 4 5 6

1 2 3 4

7 4 4

4 1 2 3 4 5 6

1 2 3 4

11 5 3

9 9 2 2 10 9 7 6 3 6 3

6 9 7 8 10

4 1 1

4 1 5 6

6

Output:

4

3

2

4

1

Explanation:

Example is self explanatory

5

7 4 2

4 1 2 3 4 5 6

1 2 3 4

7 4 3

4 1 2 3 4 5 6

1 2 3 4

7 4 4

4 1 2 3 4 5 6

1 2 3 4

11 5 3

9 9 2 2 10 9 7 6 3 6 3

6 9 7 8 10

4 1 1

4 1 5 6

6

Output:

4

3

2

4

1

Explanation:

Example is self explanatory