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

Саша хочет купить себе квартиру на улице, вдоль которой дома пронумерованы от $$$1$$$ до $$$10^9$$$ слева направо.

На этой улице находится $$$n$$$ баров, в домах с номерами $$$a_1, a_2, \ldots, a_n$$$. При этом несколько баров могут находиться в одном и том же доме, однако бары при этом считаются различными.

Саша опасается, что до момента покупки некоторые бары могут закрыться, но закроется не более $$$k$$$ из них.

Для любого дома с номером $$$x$$$ определим $$$f(x)$$$ как сумму $$$|x - y|$$$ по всем открытым барам $$$y$$$ (то есть после закрытия некоторых баров).

Саша потенциально может купить квартиру в доме с номером $$$x$$$ (где $$$1 \le x \le 10^9$$$) тогда и только тогда, когда можно выбрать не более $$$k$$$ баров для закрытия так, что после этого $$$f(x)$$$ будет минимально среди всех домов.

Определите, в скольких различных домах Саша потенциально может купить себе квартиру.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5, 0 \leq k \lt n$$$) — количество баров и максимальное количество баров, которые могут закрыться.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — номера домов, в которых расположены бары.

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

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

Для каждого набора входных данных выведите единственное целое число — количество домов, в которых Саша может купить квартиру.

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

В первом наборе входных данных никакой из баров не может закрыться, поэтому только дома с номерами $$$2$$$ и $$$3$$$ подходят. Для дома под номером $$$2$$$ сумма расстояний равна $$$|2 - 1| + |2 - 2| + |2 - 3| + |2 - 4| = 4$$$, для дома под номером $$$3$$$ сумма расстояний равна $$$|3 - 1| + |3 - 2| + |3 - 3| + |3 - 4| = 4$$$. Тогда как для дома под номером $$$1$$$ сумма расстояний будет равна $$$|1 - 1| + |1 - 2| + |1 - 3| + |1 - 4| = 6$$$, поэтому дом под номером $$$1$$$ не подходит. Также можно доказать, что Саша не может купить квартиры в других домах.

Во втором наборе входных данных подходят дома с номерами $$$6$$$ и $$$7$$$. Чтобы Саша выбрал дом под номером $$$6$$$, достаточно, чтобы ни один из баров не закрывался. Чтобы Саша выбрал дом под номером $$$7$$$, могут закрыться бары в домах $$$1$$$ и $$$6$$$. Тогда бары будут располагаться в домах под номерами $$$6$$$, $$$7$$$ и $$$7$$$.