给定一个包含 $n$ 个整数的数组 $A$ 和一个整数 $k$ ($1 \le k \le n$)。你希望将其转换为一个有序数组。

你可以对 $A$ 执行任意次数的以下操作：

• 选择 $k$ 个下标 $1 \le i_1 < i_2 < i_3 < \dots < i_k \le n$，并对这些下标处的值进行循环移位。
  • 即 $A[i_1]$ 移动到下标 $i_2$，$A[i_2]$ 移动到下标 $i_3$，$\dots$，$A[i_k]$ 移动到下标 $i_1$。
  • 注意，你选择的循环移位下标必须始终保持递增。
  • 此操作的代价为 0。
• 选择一个下标 $i$，将 $A[i]$ 加 1 或减 1。
  • 此操作的代价为 1。

求将数组转换为有序数组的最小总代价。

说明： 数组 $A$ 的下标从 1 开始。 如果数组 $X$ 满足 $X_1 \le X_2 \le X_3 \le \dots$，则称其为有序数组。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。 每个测试用例包含两行输入： 第一行包含两个空格分隔的整数 $n$ 和 $k$。 第二行包含 $n$ 个空格分隔的整数 $A_1, A_2, \dots, A_n$，即数组 $A$ 的初始值。

数据范围： $1 \le t \le 10^5$ $1 \le n \le 3 \cdot 10^5$ $1 \le k \le n$ $1 \le A[i] \le 10^9$ * 所有测试用例中 $n \cdot k$ 的总和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行包含一个整数：将 $A$ 转换为有序数组的最小代价。

样例

样例输入 1

4
4 1
6 4 3 7
4 2
6 4 3 7
4 3
6 4 3 7
4 4
6 4 3 7

样例输出 1

3
0
1
2

说明

在所有样例中，初始数组均为 $A = [6, 4, 3, 7]$。

• 对于 $k = 1$，我们从第一个元素减去 2，并给第三个元素加上 1，将数组变为 $A = [4, 4, 4, 7]$。
• 对于 $k = 2$，我们可以选择 $i_1 = 1$ 和 $i_2 = 3$，将数组转换为 $[3, 4, 6, 7]$，这是有序的。此操作代价为 0。
• 对于 $k = 3$，以下过程是最优的：
  • 选择 $i_1 = 1, i_2 = 2, i_3 = 3$。数组变为 $[3, 6, 4, 7]$。
  • 再次选择 $i_1 = 1, i_2 = 2, i_3 = 3$。数组变为 $[4, 3, 6, 7]$。
  • 从第一个元素减去 1 得到 $[3, 3, 6, 7]$。
• 对于 $k = 4$，以下过程是最优的：
  • 给第一个元素加上 1。数组变为 $[7, 4, 3, 7]$。
  • 从第二个元素减去 1。数组变为 $[7, 3, 3, 7]$。
  • 选择所有四个元素并循环移位得到 $[7, 7, 3, 3]$。
  • 再次循环移位得到 $[3, 7, 7, 3]$。
  • 再次循环移位得到 $[3, 3, 7, 7]$。