D. Неточный поиск подперестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Максима есть массив $$$a$$$ из $$$n$$$ целых чисел и массив $$$b$$$ из $$$m$$$ целых чисел ($$$m \le n$$$).

Максим считает массив $$$c$$$ длины $$$m$$$ хорошим, если элементы массива $$$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]$$$ не являются хорошими.

Максим хочет выбрать в качестве элементов массива $$$c$$$ каждый подотрезок массива $$$a$$$ длины $$$m$$$. Помогите Максиму посчитать, сколько выбранных массивов будут являться хорошими.

Иными словами, найдите количество позиций $$$1 \le l \le n - m + 1$$$ таких, что элементы $$$a_l, a_{l+1}, \dots, a_{l + m - 1}$$$ формируют хороший массив.

Входные данные

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$) — количество элементов в массивах $$$a$$$ и $$$b$$$, требуемое число совпадающих элементов.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$. Элементы массива $$$a$$$ не обязательно различные.

Третья строка каждого набора содержит $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^6$$$) — элементы массива $$$b$$$. Элементы массива $$$b$$$ не обязательно различные.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Аналогично, гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите количество хороших подотрезков массива $$$a$$$.

Пример
Входные данные
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
Выходные данные
4
3
2
4
1
Примечание

В первом примере все подотрезки являются хорошими.

Во втором примере хорошие подотрезки начинаются с позиций $$$1$$$, $$$2$$$ и $$$3$$$.

В третьем примере хорошие подотрезки начинаются с позиций $$$1$$$ и $$$2$$$.