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

Иван играет в старый шутер под названием «Heretic». Он застрял на одном из последних уровней этой игры, поэтому ему нужна помощь в убийстве монстров.

Основная часть уровня представляет собой большой коридор (настолько большой и узкий, что его можно представить в виде бесконечной координатной прямой). Коридор разделен на две части; давайте считать, что точка $$$x = 0$$$ разделяет эти части.

Правая часть коридора заполнена $$$n$$$ монстрами. Для каждого монстра задана его начальная координата $$$x_i$$$ (поскольку все монстры находятся в правой части, все $$$x_i$$$ положительны).

Левая часть коридора заполнена ловушками-давилками. Если какой-то монстр попадает в левую часть коридора или в начало координат (то есть его текущая координата становится меньше или равна $$$0$$$), он мгновенно убивается ловушкой.

Основным оружием, которое Иван использует для убийства монстров, является Жезл Феникса. Он может запустить снаряд, который взрывается при ударе, уничтожая каждого монстра, оказавшегося в точке взрыва, и разбрасывая всех остальных монстров. Предположим, что Иван запускает снаряд в точку $$$c$$$. Тогда каждый монстр либо погибает от взрыва, либо отбрасывается. Пусть текущая координата какого-то монстра будет $$$y$$$, тогда:

  • если $$$c = y$$$, то монстр убит;
  • если $$$y < c$$$, то монстр отбрасывается на $$$r$$$ влево, поэтому его текущая координата становится $$$y - r$$$;
  • если $$$y > c$$$, то монстр отбрасывается на $$$r$$$ вправо, поэтому его текущая координата становится $$$y + r$$$.

Иван собирается убивать монстров следующим образом: выбирать некоторую целочисленную точку $$$d$$$, запускать снаряд в эту точку, затем ждать, пока снаряд не взорвется, и все монстры, которых отбрасывает в левую часть коридора, не будут убиты ловушками-давилками, затем, если хотя бы один монстр еще жив, выбирать другую целую точку (возможно, ту, которая уже использовалась) и запускать снаряд туда, и так далее.

Какое минимальное количество снарядов должен запустить Иван, чтобы убить всех монстров? Можете считать, что Иван оптимально выбирает цель, когда стреляет из Жезла Феникса.

Вам нужно ответить на $$$q$$$ независимых запросов.

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

Первая строка содержит целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Первая строка каждого запроса содержит два целых числа $$$n$$$ и $$$r$$$ ($$$1 \le n, r \le 10^5$$$) — количество монстров и расстояние, на которое монстры отбрасываются от точки взрыва.

Вторая строка каждого запроса содержит $$$n$$$ целых чисел $$$x_i$$$ ($$$1 \le x_i \le 10^5$$$) — начальные позиции монстров.

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

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

На каждый запрос выведите одно целое число — минимальное количество выстрелов из Жезла Феникса, чтобы убить всех монстров.

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

В первом тестовом примере Иван действует следующим образом:

  • стреляет в точку $$$3$$$, первый монстр умирает от ловушки-давилки в точке $$$-1$$$, второй монстр умирает от взрыва, третьего монстра отбрасывает в точку $$$7$$$;
  • стреляет в точку $$$7$$$, третий монстр умирает от взрыва.

Во втором тестовом примере Иван действует следующим образом:

  • стреляет в точку $$$5$$$, первый и четвертый монстры умирают от взрыва, второго монстра отбрасывает в точку $$$1$$$, третьего монстра отбрасывает в точку $$$2$$$;
  • стреляет в точку $$$2$$$, первый монстр умирает от ловушки-давилки в точке $$$0$$$, второй монстр умирает от взрыва.