У вас есть плейлист из N видео. Длительность i-го видео — d_i минут. Реклама показывается между видео, если соблюдается одно из следующих условий: - с показа последней рекламы просмотрено 3 видео; - с показа последней рекламы прошло хотя бы k минут. Вам

ограничение по времени на тест: 3 s .
ограничение по памяти на тест: 1024 MB
В вашем плейлисте на сайте MeValve сейчас содержится \( n \) очень интересных и познавательных видео. \( i \)-е видео длится ровно \( d_{i} \) минут.

MeValve в своей обычной манере увеличил частоту и продолжительность показа рекламы. Во вселенной добра и справедливости, где вы находитесь, реклама на MeValve показывается только МЕЖДУ видео. После видео реклама показывается тогда и только тогда, когда соблюдается любое из условий ниже:
- с показа последней рекламы было просмотрено 3 видео;
- с показа последней рекламы прошло хотя бы \( k \) минут.

Для выполнения домашней работы вам срочно нужно посмотреть все \( \boldsymbol{n} \) видео в вашем плейлисте. Зная, что вы только что просмотрели рекламный ролик, выберите такой порядок просмотра видео, чтобы минимизировать количество просмотренных рекламных вставок. Следующее видео начинается сразу после того, как заканчивается предыдущее видео либо реклама, и после последнего ролика рекламу смотреть не обязательно (шах и мат, Googleплекс) |

Входные данные
В первой строке записано единственное целое число \( t(1 \leq t \leq 100000) \) - Количество наборов входных данных.
Первая строка каждого набора состоит из пары натуральных чисел \( n \) и \( k(1 \leq n \leq 100000,1 \leq k \leq 30000) \) - количество видео и временной интервал между показами рекламы соответственно.

В следующей строке даны \( n \) чисел \( d_{1}, d_{2}, \ldots, d_{n}\left(1 \leq d_{i} \leq 10000\right) \) - продолжительности роликов в плейлисте.
Сумма \( n \) по всем тестам не превосходит \( 10^{6} \).
Выходные данные
В ответ на каждый тестовый набор выведите минимальное количество рекламных роликов, которое необходимо посмотреть.
Пример
\begin{tabular}{|l|l|}
\hline входные данные & Скопировать \\
\hline \multicolumn{2}{|l|}{5} \\
\hline 825 & \\
\hline \multicolumn{2}{|l|}{\( \begin{array}{llllllll}4 & 5 & 18 & 3 & 17 & 17 & 18 & 14\end{array} \)} \\
\hline \multicolumn{2}{