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

Вы являетесь автором раунда Codeforces и подготовили $$$n$$$ задач, которые вы собираетесь задать, причем задача $$$i$$$ имеет сложность $$$a_i$$$. Вы будете выполнять следующий процесс:

  • удалить некоторые (возможно, ноль) задач из списка;
  • переставить оставшиеся задачи в любом порядке, который вы пожелаете.

Раунд считается сбалансированным, если и только если абсолютная разница между сложностью любых двух последовательных задач не превышает $$$k$$$ (то есть меньше или равен $$$k$$$).

Какое минимальное количество задач нужно удалить, чтобы расстановка задач была сбалансированной?

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

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

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

Обратите внимание, что сумма $$$n$$$ по всем тестам не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
7
5 1
1 2 4 5 6
1 2
10
8 3
17 3 1 20 12 5 17 12
4 2
2 4 6 8
5 3
2 3 19 10 8
3 4
1 10 5
8 1
8 3 1 4 5 10 7 3
Выходные данные
2
0
5
0
3
1
4
Примечание

В первом примере мы можем удалить первые $$$2$$$ задачи и составить набор, используя задачи со сложностями $$$[4, 5, 6]$$$, с разницей между соседними задачами равной $$$|5 - 4| = 1 \leq 1$$$ и $$$|6 - 5| = 1 \leq 1$$$.

Во втором примере мы можем взять одну задачу и составить раунд, используя задачу со сложностью $$$10$$$.