C. Ина с Горы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы подготовить своих осьминогов «Такодачи» к правлению миром, Ниномае Ина-нис, также известная как Ина с Горы, приказала Хишимачи Суйсей бросать в них валуны. Ина просит вас, Кирю Коко, помочь выбрать, как именно бросать валуны.

В одну линию на горе Ины находятся $$$n$$$ осьминогов, они пронумерованы $$$1, 2, \ldots, n$$$. $$$i$$$-й осьминог изначально имеет здоровье, равное $$$a_i$$$, где $$$1 \leq a_i \leq k$$$.

Каждый валун падает на последовательных осьминогов с номерами $$$l, l+1, \ldots, r$$$, где $$$1 \leq l \leq r \leq n$$$. Вы можете выбрать числа $$$l$$$ и $$$r$$$ для каждого валуна произвольным образом.

Каждый валун уменьшает здоровье каждого осьминога, на которого он падает, на $$$1$$$. Однако осьминоги бессмертны, поэтому как только здоровье осьминога становится равно $$$0$$$, он немедленно восстановит свое здоровье до $$$k$$$.

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

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le k$$$) — начальные значения здоровья осьминогов.

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

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

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

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

В первом наборе входных данных минимальное количество бросков валуна равно $$$2$$$:

  • Бросить первый валун между $$$[l,r] = [1,3]$$$. Тогда значения здоровья осьминогов станут $$$[3, 1, 3, 3]$$$.
  • Бросить второй валун между $$$[l,r] = [2,2]$$$. Тогда значения здоровья осьминогов станут $$$[3, 3, 3, 3]$$$.

Во втором наборе минимальное количество бросков валуна равно $$$4$$$. Диапазоны $$$[l,r]$$$ равны $$$[1,7], [2, 6], [3, 5], [4, 4]$$$.