该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

旅行者在提瓦特大陆上发现了一群 $\rm N$ 只史莱姆 , 它们挡住了旅行者的必经之路

旅行者发现这一群史莱姆十分特殊：它们中的每一只史莱姆血量都为 $\rm 1\sim N$ 之间的一个整数 , 且没有任何两只史莱姆血量相同

史莱姆们排成了一队

旅行者十分谨慎 , 他觉得如果上来就遇到一只血量很厚的史莱姆对他很不利 , 所以他希望这个史莱姆队伍最后是按照血量升序排序的(即血量最少的史莱姆排在第一个 , 第二少的排在第二个 , 以此类推)

派蒙有一种能力 , 来帮助旅行者：

• 派蒙可以选择 $\rm K$ 个史莱姆；

• 然后她会将将这 $\rm K$ 个史莱姆按照血量升序排序后插到队尾

但是这种操作会消耗旅行者的纠缠之缘 , 所以派蒙希望可以尽量少的使用能力来达到旅行者的目标

派蒙的数学不好 , 请你告诉她她至少需要使用几次能力？

【举个栗子】

当队伍中的史莱姆血量分别为 $\rm [2,3,1,4]$ , $\rm K=2$ 时：

派蒙可选红色部分

将其变为

输入格式

第一行输入一个整数 $\rm T$ , 表示 $\rm T$ 组询问

• 每组询问第一行输入两个整数 $\rm N,K$；

• 每组询问第二行输入 $\rm N$ 个整数表示初始时史莱姆序列中各个史莱姆的血量

输出格式

每组询问输出一行一个整数表示派蒙使用能力的最少次数

3
3 2
1 2 3
3 1
3 1 2
4 2
2 3 1 4

0
1
2

样例2

数据规模

对于 $15\%$ 的数据 $\rm 1 \leq N \leq 12$

对于 $45\%$ 的数据 $\rm 1 \leq N \leq 5000$

对于 $100\%$ 的数据 $\displaystyle \rm 1 \leq T \leq 10, 1 \leq \sum N \leq 10^5$