D2. Нарезка морковки (cложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие между простой и сложной версиями — ограничения на $$$n$$$, $$$k$$$, $$$a_i$$$ и сумму $$$n$$$ по всем наборам входных данных. Вы можете делать взломы, только если обе версии задачи решены.

Обратите внимание на нестандартное ограничение по памяти.

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$ и целое число $$$k$$$.

Стоимость массива целых чисел $$$p_1, p_2, \ldots, p_n$$$ длины $$$n$$$ равна $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$

Здесь $$$\lfloor \frac{x}{y} \rfloor$$$ обозначает целую часть от деления $$$x$$$ на $$$y$$$. Найдите минимальную возможную стоимость массива $$$p$$$, такого что $$$1 \le p_i \le k$$$ для всех $$$1 \le i \le n$$$.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке даны два числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 10^5$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 10^5$$$).

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

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

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

Пример
Входные данные
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3
Выходные данные
2
0
13
1
4
7
0
Примечание

В первом наборе входных данных оптимальный массив $$$p = [1, 1, 1, 2, 2]$$$. Массив значений $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ для данного массива равен $$$[4, 5, 6, 4, 5]$$$. Стоимость $$$p$$$ равна $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$. Можно показать, что не существует массива (удовлетворяющего требованию из условия) с меньшей стоимостью.

Во втором наборе входных данных один из оптимальных массивов $$$p = [12, 12, 12, 12, 12]$$$. Все значения $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ для данного массива равны $$$0$$$.

В третьем наборе входных данных единственный возможный массив $$$p = [1, 1, 1]$$$.