说明

你正在管理一个由 $n$ 架无人机组成的机队，每架无人机有一个能量等级 $a_1, \dots, a_n$。同时，给定一个正整数 $k$，它表示允许共享相同能量等级的无人机的最大数量。

为了防止过载，无人机会自动执行能量平衡操作，流程如下：当存在某个能量等级出现次数严格大于 $k$ 次时，它们执行以下步骤：

• 首先，标记每一架能量值 $a_i$ 已经在前面出现过的无人机 $i$（即存在 $j < i$ 满足 $a_j = a_i$）；
• 然后，对于每架被标记的无人机，其能量值增加 $1$ 单位；
• 最后，清除所有标记。

当没有任何能量等级出现次数超过 $k$ 次时，过程停止。请确定将会执行多少次能量平衡操作。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$（$1 \le k \le n \le 2 \cdot 10^5$）——分别表示无人机的数量和允许拥有相同能量等级的无人机的最大数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2n$）——无人机的初始能量等级。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示执行的能量平衡操作的次数。

5
6 3
1 1 1 1 1 1
5 1
1 3 2 1 4
16 2
6 3 7 5 13 6 7 6 3 5 13 7 6 4 3 6
16 3
6 3 7 5 13 6 7 6 3 5 13 7 6 4 3 6
16 4
6 3 7 5 13 6 7 6 3 5 13 7 6 4 3 6

3
4
14
5
4

提示

样例 1 解释

在第一个测试用例中，无人机的能量等级变化如下：

• 初始时：$[1, 1, 1, 1, 1, 1]$；
• 第 1 次操作后：$[1, 2, 2, 2, 2, 2]$；
• 第 2 次操作后：$[1, 2, 3, 3, 3, 3]$；
• 第 3 次操作后：$[1, 2, 3, 4, 4, 4]$。

3 次操作后，每个能量等级最多出现 3 次，因此过程停止。

在第二个测试用例中，能量等级变化如下：$[1, 3, 2, 1, 4] \to [1, 3, 2, 2, 4] \to [1, 3, 2, 3, 4] \to [1, 3, 2, 4, 4] \to [1, 3, 2, 4, 5]$。过程在 4 次操作后停止。

翻译由 DeepSeek 完成