给你一个长度为 $$$n$$$ 的排列$$$^\dagger$$$ $$$p$$$ 和一个正整数 $$$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, \颜色{红色}{3},\颜色{红色}{5}]$$$。
求按升序对排列进行排序所需的最少操作数。可以证明,这样做总是可以的。
$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 对排列进行排序所需的最少操作数。可以证明,这样做总是可以的。
示例
输入 #1
4 3 2 1 2 3 3 1 3 1 2 4 2 1 3 2 4 4 2 2 3 1 4
输出 #1
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}]$$$。