有一个大小为 $n$ 的循环缓冲区，读取器位于第 $1$ 到第 $k$ 个位置（包含边界）。设 $a_i$ ($1 \le i \le n$) 为缓冲区初始时第 $i$ 个位置上的整数。此外，$a_1, a_2, \dots, a_n$ 构成了一个 $n$ 的排列。

我们要按递增顺序访问从 $1$ 到 $n$ 的所有整数（包含边界）。只有当一个整数位于读取器所在的位置（即位于前 $k$ 个位置）时，才能被访问。如果某个整数无法被访问，我们可以向任意方向移动整个缓冲区任意次数。

• 如果我们将缓冲区向左移动一次，第 $i$ 个位置上的整数将移动到第 $(i-1)$ 个位置（如果 $i > 1$），第 $1$ 个位置上的整数将移动到第 $n$ 个位置。
• 如果我们将缓冲区向右移动一次，第 $i$ 个位置上的整数将移动到第 $(i+1)$ 个位置（如果 $i < n$），第 $n$ 个位置上的整数将移动到第 $1$ 个位置。

请问为了按递增顺序访问所有整数，最少需要移动缓冲区的次数是多少？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 10^6$)，分别表示缓冲区的大小和读取器的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示缓冲区初始时第 $i$ 个位置上的整数。

保证给定的 $n$ 个整数构成一个 $n$ 的排列。同时保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示为了按递增顺序访问所有整数，最少需要移动缓冲区的次数。

样例

输入 1

2
5 3
2 4 3 5 1
1 1
1

输出 1

3
0

说明

对于第一个样例测试数据：

• 向右移动一次，缓冲区变为 $\{1, 2, 4, 3, 5\}$。此时 $1$ 和 $2$ 位于前 $3$ 个位置，可以按顺序访问。
• 向左移动两次，缓冲区变为 $\{4, 3, 5, 1, 2\}$。此时 $3, 4$ 和 $5$ 位于前 $3$ 个位置，可以按顺序访问。