B. Вакцинация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Итан управляет станцией вакцинации, чтобы помогать людям бороться с сезонным гриппом. Он анализирует исторические данные, чтобы разработать оптимальную стратегию использования вакцины.

Пусть в конкретный день на станцию вакцинации придут $$$n$$$ пациентов. Пациент с номером $$$i$$$ придёт в момент времени $$$t_i$$$. Каждого пациента можно попросить подождать не более $$$w$$$ моментов времени, то есть $$$i$$$-й пациент может получить вакцину в моменты времени $$$t_i, t_i + 1, \ldots, t_i + w$$$.

Вакцины поставляются в упаковках, каждая упаковка состоит из $$$k$$$ доз. Каждому пациенту требуется ровно одна доза. Пакеты хранятся в специальном холодильнике. После того, как пачку вынули из холодильника и открыли, ее уже нельзя положить обратно. Время жизни вакцины вне холодильника составляет $$$d$$$ моментов времени. Таким образом, если упаковка была вынута из холодильника и открыта в момент $$$x$$$, дозы из этой упаковки можно использовать для вакцинации пациентов в моменты $$$x, x + 1, \ldots, x + d$$$. В момент $$$x + d + 1$$$ все оставшиеся неиспользованные дозы этой пачки выбрасываются.

Предположим, что на станции вакцинации достаточно персонала для проведения произвольного количества операций в каждый момент времени. Какое минимальное количество упаковок вакцин требуется для вакцинации всех $$$n$$$ пациентов?

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

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

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

Вторая строка каждого набора входных данных содержит неубывающую последовательность $$$t_1, t_2, \ldots, t_n$$$ ($$$0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^6$$$). $$$i$$$-м элементом этой последовательности является момент прихода $$$i$$$-го пациента на станцию вакцинации.

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

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

Выведите одно целое число — минимальное количество упаковок с вакциной, необходимое для вакцинации всех $$$n$$$ пациентов.

Пример
Входные данные
5
6 3 5 3
1 2 3 10 11 18
6 4 0 0
3 3 3 3 3 4
9 10 2 2
0 1 2 3 4 5 6 7 8
3 10 3 6
10 20 30
5 5 4 4
0 2 4 6 8
Выходные данные
2
3
2
3
1
Примечание

В первом наборе входных данных первая упаковка может быть открыта в момент времени $$$1$$$ для вакцинации пациента $$$1$$$. Затем дозы из этой упаковки будут использованы в моменты времени $$$2$$$ и $$$3$$$ для пациентов $$$2$$$ и $$$3$$$ соответственно. Далее персоналу необходимо попросить пациентов $$$4$$$ и $$$5$$$ дождаться момента $$$13$$$. В момент $$$13$$$ персонал открывает вторую упаковку вакцины и обслуживает пациентов $$$4$$$ и $$$5$$$. Наконец, последний пациент приходит в момент $$$18$$$ и сразу же получает последнюю дозу из второй упаковки, пока она ещё не испортилась.

Во втором наборе входных данных вакцина может быть использована только в тот момент времени, когда её достают из холодильника. Более того, все пациенты хотят быть обслужены именно в тот момент, когда они приходят. Это означает, что персонал должен открыть две упаковки в момент $$$3$$$ и использовать пять доз для пациентов $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$. Из этих двух упаковок останется три дозы, но их нельзя использовать для пациента $$$6$$$. Когда пациент $$$6$$$ приходит в момент $$$4$$$, персоналу необходимо открыть новую упаковку, чтобы использовать только одну дозу из неё.