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

Люк любит поесть. Перед ним $$$n$$$ стопок еды, выстроенных по прямой линии. В $$$i$$$-й стопке находится $$$a_i$$$ единиц еды.

Люк будет идти от $$$1$$$-й стопки к $$$n$$$-й стопке, и он хочет съесть каждую стопку еды, не возвращаясь назад. Когда Люк достигает $$$i$$$-й стопки, он может съесть ее тогда и только тогда, когда $$$|v - a_i| \leq x$$$, где $$$x$$$ — фиксированное целое число, а $$$v$$$ — пищевое желание Люка.

Прежде чем Люк начнет ходить, он может установить $$$v$$$ в любое целое число. Кроме того, для каждого $$$i$$$ ($$$1 \leq i \leq n$$$) Люк может изменить свое пищевой желание на любое целое число до того, как он съест $$$i$$$-ю стопку.

Найдите минимальное количество изменений, необходимое для того, чтобы съесть каждую стопку еды.

Обратите внимание, что первоначальный выбор $$$v$$$ не считается изменением.

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

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

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

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

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

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

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

Пример
Входные данные
7
5 3
3 8 5 6 7
5 3
3 10 9 8 7
12 8
25 3 3 17 8 6 1 16 15 25 17 23
10 2
1 2 3 4 5 6 7 8 9 10
8 2
2 4 6 8 6 4 12 14
8 2
2 7 8 9 6 13 21 28
15 5
11 4 13 23 7 10 5 21 20 11 17 5 29 16 11
Выходные данные
0
1
2
1
2
4
6
Примечание

В первом наборе входных данных Люк может установить $$$v$$$ в $$$5$$$ до того, как он начнет ходить. И он может идти прямо, чтобы съесть каждую стопку еды, не меняя $$$v$$$.

Во втором наборе входных данных Люк может установить $$$v$$$ в $$$3$$$ до того, как он начнет ходить. И он может поменять $$$v$$$ на $$$10$$$, прежде чем съест вторую стопку. После этого он может идти прямо, чтобы съесть оставшуюся еду, не меняя $$$v$$$.

В четвертом наборе входных данных Люк может установить $$$v$$$ в $$$3$$$ до того, как начнет ходить. И он может поменять $$$v$$$ на $$$8$$$ до того, как съест шестую стопку. После этого он может идти прямо, чтобы съесть оставшуюся еду, не меняя $$$v$$$.

В пятом наборе входных данных Люк может установить $$$v$$$ в $$$4$$$ до того, как начнет ходить. И он может поменять $$$v$$$ на $$$6$$$ до того, как съест четвертую стопку. Тогда он может поменять $$$v$$$ на $$$12$$$ до того, как съест седьмую стопку. После этого он может идти прямо, чтобы съесть оставшуюся еду, не меняя $$$v$$$.