题目描述

Maxim 有一个包含 $n$ 个整数的数组 $a$ 和一个包含 $m$ 个整数的数组 $b$（其中 $m \leq n$）。

Maxim 认为长度为 $m$ 的数组 $c$ 是好的，如果 $c$ 的元素可以通过重新排列，使得至少 $k$ 个元素与数组 $b$ 的元素相匹配。

例如，如果 $b = [1, 2, 3, 4]$ 且 $k = 3$，那么数组 $[4, 1, 2, 3]$ 和 $[2, 3, 4, 5]$ 是好的（它们可以重新排列为 $[1, 2, 3, 4]$ 和 $[5, 2, 3, 4]$），而数组 $[3, 4, 5, 6]$ 和 $[3, 4, 3, 4]$ 则不是好的。

Maxim 想要选择数组 $a$ 中长度为 $m$ 的每个子段作为数组 $c$ 的元素。帮助Maxim计算有多少个选定的数组将是好的。

换句话说，找出位置 $1 \leq l \leq n - m + 1$ 的数量，使得元素 $a_l, a_{l+1}, \dots, a_{l+m-1}$ 形成一个好的数组。

输入格式

The first line contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.

The first line of each test case contains three integers $n$ , $m$ , and $k$ ( $1 \le k \le m \le n \le 2 \cdot 10^5$ ) — the number of elements in arrays $a$ and $b$ , the required number of matching elements.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ) — the elements of array $a$ . Elements of the array $a$ are not necessarily unique.

The third line of each test case contains $m$ integers $b_1, b_2, \dots, b_m$ ( $1 \le b_i \le 10^6$ ) — the elements of array $b$ . Elements of the array $b$ are not necessarily unique.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ . Similarly, it is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$ .

样例 #1

样例输入 #1

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

样例输出 #1

4
3
2
4
1