【问题描述】

$Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturers in the world.$ 每天, 该公司生产 $𝑛$ 台 $CPU$ 并销售到世界各地。

$ACM$ 公司的质检部门会对生产出的 $CPU$ 进行成组测试，对一组（若干个）$CPU$ 进行测试的方法如下：

1. 随机从该组 $CPU$ 中选取$𝑚$ 对（即 $2𝑚$ 台），若总数不足 $2𝑚$ 台，则选取尽量多对。
2. 对于每一对 $CPU$，测量它们之间的 $Relative Performance Difference (𝑅𝑃𝐷)$，并把第 $𝑖$ 对的𝑅$𝑃𝐷$记为 $𝐷_i$。$𝑅𝑃𝐷$的计算方法在后面给出。
3. 该组 $CPU$ 的 $Sqared Performance Difference (𝑆𝑃𝐷)$ 由以下公式给出：

4. 该组$CPU$通过质检，当且仅当 $𝑆𝑃𝐷 ≤ 𝑘,$ 其中$𝑘$ 是给定常数。

$ACM$ 公司生产的 $CPU$性能很好，而质检部门制定的标准更是过于严格。通

常他们把$𝑛$台$CPU$作为一整组进行测试，这导致一些性能良好的 $CPU$无法通过测试，生产部门对此颇有微词。作为质检部门的领导，小$S$ 在不更改质检测试流程的前提下，想出了这样一个主意：如果能够把 $𝑛$台$CPU$恰当地分成连续的

若干段，使得每段$CPU$ 都能够通过成组测试，就可以解决当下的问题。

现在，小 $S$ 已经知道了$𝑛$ 台各自的性能表现$𝑃_1 … 𝑃_n$ ，两台$CPU$ 的$𝑅𝑃𝐷$被定义为它们性能表现的差的绝对值。请你帮忙计算一下，至少把这些 $CPU$分成多少段，才能使得每一段都能通过成组测试。

【输入格式】

每个测试点包含多组数据，第一行一个整数$𝑇$ 给出数据组数。

对于每组数据，第一行三个整数 $𝑛, 𝑚, 𝑘，$第二行$𝑛$个整数$𝑃_1 … 𝑃_n 。$

【输出格式】

对于每组数据，输出一个整数表示答案。

样例

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9

2
1

【数据规模与约定】

对于 20%的数据，$1 ≤ 𝑛 ≤ 10^2 。$

对于 40%的数据，$1 ≤ 𝑛 ≤ 10^3 。$

对于另外 10%的数据，$𝑘 = 0。$

对于另外 10%的数据，$0 ≤ 𝑘 ≤ 1。$

对于另外 10%的数据，$𝑚 = 1。$

对于另外 10%的数据，$1 ≤ 𝑚 ≤ 2。$

对于 90%的数据，$0 ≤ 𝑘 ≤ 10^12 。$

对于 100%的数据，$𝑇 ≤ 12, 1 ≤ 𝑛, 𝑚 ≤ 5 ⋅ 10^5 , 0 ≤ 𝑘 ≤ 10^{18}, 0 ≤ 𝑃_i ≤ 2^{20} 。$

来源

全国信息学奥林匹克联赛（NOIP2016）复赛模拟试题 提高组 day2