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

Вам дана перестановка$$$^\dagger$$$ $$$p$$$ длины $$$n$$$ и положительное число $$$k \le n$$$.

За одну операцию вы:

  • Выбираете $$$k$$$ различных элементов $$$p_{i_1}, p_{i_2}, \ldots, p_{i_k}$$$.
  • Удаляете их из массива и добавляете эти элементы в конец массива в отсортированном по возрастанию порядке.

Например, если $$$p = [2,5,1,3,4]$$$ и $$$k = 2$$$, и вы выберете $$$5$$$ и $$$3$$$ как элементы для операции, то операция будет выглядеть так: $$$[2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}]$$$.

Найдите минимальное число операций, которое необходимо сделать, чтобы отсортировать массив по возрастанию. Можно показать, что это всегда возможно сделать.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но $$$4$$$ присутствует в массиве).

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

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

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$). Гарантируется, что $$$p$$$ — перестановка.

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

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

Для каждого набора входных данных выведите одно число — минимальное количество операций, которое необходимо сделать, чтобы отсортировать массив. Можно показать, что это всегда возможно.

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

В первом наборе входных данных массив уже отсортирован.

Во втором наборе можно выбрать число $$$3$$$ и перестановка станет отсортированной: $$$[\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}]$$$.

В третьем наборе входных данных можно выбрать $$$3$$$ и $$$4$$$, тогда перестановка станет отсортированной: $$$[1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}]$$$.

Можно показать, что в четвертом наборе за $$$1$$$ операцию отсортировать массив невозможно. А за две операции можно отсортировать так: в первой операции выбрать элементы $$$2$$$ и $$$1$$$, а во второй выбрать $$$3$$$ и $$$4$$$. Тогда перестановка станет отсортированной: $$$[\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}]$$$.