B. Задача из Чебаркуля
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и целое число $$$k$$$.

Найдите количество чисел $$$1 \le i \le k$$$, таких что во всех подпоследовательностях$$$^{\text{∗}}$$$ массива $$$a$$$ длины $$$k$$$ на $$$i$$$-й позиции находится одно и то же число.

$$$^{\text{∗}}$$$Последовательность $$$b$$$ является подпоследовательностью $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

В первой строке каждого набора содержатся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

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

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

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

Пример
Входные данные
7
1 1
1
3 1
2 2 3
4 2
1 1 1 1
4 2
1 2 1 2
4 4
4 1 4 2
5 3
1 2 2 2 5
6 5
1 1 2 2 1 1
Выходные данные
1
0
2
0
4
1
3
Примечание

В первом наборе входных данных у массива $$$a$$$ существует ровно одна подпоследовательность длины $$$1$$$, поэтому ответ равен единице.

Во втором наборе входных данных у массива $$$a$$$ существует три подпоследовательности длины $$$1$$$: $$$[a_1]$$$, $$$[a_2]$$$ и $$$[a_3]$$$. Ответ равен нулю, так как на первой позиции может быть как число $$$2$$$, так и число $$$3$$$.

В третьем наборе входных данных у массива $$$a$$$ все подпоследовательности длины $$$2$$$ равны $$$[1, 1]$$$, поэтому ответ равен двум.

В четвёртом наборе входных данных у массива $$$a$$$ есть шесть подпоследовательностей длины $$$2$$$. Нам достаточно рассмотреть две из них: $$$[a_1, a_4] = [1, 2]$$$ и $$$[a_2, a_3] = [2, 1]$$$. Ответ для этого набора входных данных равен нулю, так как на обеих позициях может быть как единица, так и двойка.

В пятом наборе входных данных у массива $$$a$$$ существует ровно одна подпоследовательность длины $$$4$$$, поэтому ответ равен четырём.