在一实的元旦晚会中，谢老师给图灵班的学生出了一道智力游戏：在地上有$n$个篮子，每个篮子里都有若干个硬币，第$i$个篮子硬币的数量用$a_i$来表示，那$n$个篮子的硬币数量分别为 $a_1,a_2,…,a_n$。谢老师给出了一些操作，可以用一系列的操作，让每一个篮子里硬币的数量都相等。

具体操作如下：

1. 在$n$个篮子中选取连续的一段区域，并且选取的区域中篮子个数不超过$k$个。
2. 对于选中的一段区域里，可以对区域中每一个篮子重新往里面添加或者去掉一些硬币，当然也可以保持篮子里原来的硬币数量不变。注意对于每一个篮子的操作是独立的。

现在谢老师想让图灵班的学生们通过这一系列的操作，让每个篮子里面的硬币数量都相等，最少需要多少操作？

第一次完成任务的学生会得到丰厚的奖品，现在你很想拿到这个奖品，于是你决定用编程来完成这个任务。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$个空格隔开的整数 $a_1,a_2,…,a_n$。

输出格式

每组数据输出一行结果，表示最少需要进行的操作次数。

数据范围

对于前三个测试点，$1≤k≤n≤10$。 对于全部测试点，$1≤T≤10^4,1≤k≤n≤10^5,1≤a_i≤100$，保证所有 $T$ 个 $n$ 的和不超过$10^5$。

输入样例：

3
10 2
1 1 2 2 1 1 2 2 2 1
7 1
1 2 3 4 5 6 7
10 3
1 3 3 3 3 1 2 1 3 3

输出样例：

3
6
2

样例解释

样例数据1：

将 $1 \sim 2$这一段选取成一个区域，往该区域里面所有篮子添加硬币使每个篮子硬币数量变为 $2$

此时所有的篮子硬币数量为：

2 2 2 2 1 1 2 2 2 1

再将 $4 \sim 5$ 这一段区域里的篮子里的硬币添加硬币使每个篮子硬币数量变为 $2$

此时所有的篮子硬币数量为：

2 2 2 2 2 2 2 2 2 1

最后将 $10$ 这一段区域里的篮子里的硬币添加硬币使每个篮子硬币数量变为 $2$

2 2 2 2 2 2 2 2 2 2

共操作 $3$ 次

样例数据2：

选取$2$ 、$3$、$4$、$5$、$6$、$7$这六段区域的篮子硬币进行修改。

最终所有篮子的硬币数量为：

1 1 1 1 1 1 1

共操作 $6$ 次

样例数据3： 选取$1$、$6\sim8$ 这两段区域的篮子硬币进行修改。

最终所有篮子的硬币数量为：

3 3 3 3 3 3 3 3 3 3

共操作 $2$ 次