题目描述

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

对于新手而言，他们可能会直接忽略那些过难的题目；而对于竞赛专家来说，一道简单的题目几乎毫无意义。此外，如果一场比赛同时包含简单题和困难题，非但不能让双方满意，反而会因为这两种原因让所有人都感到不快。

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

具体来说，假设题目的难度可以用一个正整数 $i$ 来衡量，数值越大代表题目越难。在 Yu 的设计中，一场比赛由若干道难度连贯的题目组成。形式化地，如果一场比赛包含 $k$ 道题目，那么它们的难度必须依次为 $i, i+1, \dots, i+k-1$。这是因为，如果存在两道难度相同的题目，它们在比赛中的作用就会雷同，这并不合适；而如果两道题目难度差距过大，又将出现前文所述的问题。举例来说，难度为 $1, 2, 3, 4, 5$ 的比赛显然是一场简单比赛，而难度为 $5, 6, 7, 8, 9$ 的比赛则可以是困难比赛。

Yu 拥有数量庞大的题目，并已经度量了所有题目的难度。现在，他希望尽可能多地举办比赛。你知道他最多能举办多少场比赛吗？

输入格式

第一行有一个整数 $T$（$1 \le T \le 10$），表示有 $T$ 组测试数据。每组测试数据由两行组成。

对于每组测试数据，第一行包含两个整数 $N$ 和 $K$（$1 \le K \le N \le 100,000$），其中 $N$ 表示难度种类的总数，$K$ 表示一场比赛所需的题目数量。第二行包含 $N$ 个数 $a[i]$（$0 \le a[i] \le 10^9$），第 $i$ 个数表示难度为 $i$ 的题目数量。

输出格式

对于每组测试数据，输出一个整数，表示 Yu 最多可以举办的比赛场数。

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

2
5
6

提示

翻译由 DeepSeek V4 Pro 完成