作为编程竞赛的赞助商，Yu 需要考虑许多情况。最近，他发现题目的难度可能是一个关键因素。

对于新手来说，他们可能会直接忽略太难的题目；而对于竞赛老手来说，简单的题目几乎毫无意义。此外，如果一场比赛既包含简单题又包含难题，它既不能满足新手，也不能满足老手，反而会因为这两个原因让他们感到不快。

因此，Yu 想到了一个主意：举办不同类型的比赛！新手倾向于参加所谓的“简单比赛”，而不会参加“困难比赛”。

具体来说，假设一个问题的难度可以用一个正整数 $i$ 来衡量。数字越大，题目越难。在 Yu 的设计中，一场比赛的题目难度应该是连续的。形式化地说，如果一场比赛有 $k$ 道题，它们的难度必须分别是 $i, i+1, \dots, i+k-2, i+k-1$。这是因为如果两道题难度相同，它们在比赛中的功能就会重复，这并不好；而如果两道题的难度差距过大，就会出现上述提到的问题。

因此，难度为 $1, 2, 3, 4, 5$ 的比赛显然是一场简单比赛，而难度为 $5, 6, 7, 8, 9$ 的比赛则是一场困难比赛。

Yu 有大量的题目，并且他已经测量了所有题目的难度。现在，他想举办尽可能多的比赛，每场比赛都恰好包含 $k$ 道题（给定整数 $k$）。请帮助他计算最多可以举办多少场比赛。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 个测试用例，每个测试用例包含两行。

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 100000$)，其中 $n$ 表示难度的种类，$k$ 表示一场比赛应包含的题目数量。第二行包含 $n$ 个整数，第 $i$ 个整数 $a[i]$ ($0 \le a[i] \le 10^9$) 表示难度为 $i$ 的题目数量。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 Yu 最多可以举办的比赛数量。

样例

样例输入 1

4
3 2
1 2 1
6 3
1 5 3 4 7 6
9 4
2 7 1 3 6 5 8 9 4
3 3
1000000000 1000000000 1000000000

样例输出 1

2
5
6
1000000000