Decription PDF

Description

Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturers in the world. 每天, 该公司生产 \(n\) 台 CPU 并销售到世界各地。ACM 公司的质检部门会对生产出的CPU进行成组测试，对一组（若干个）CPU 进行测试的方法如下：
1. 随机从该组 CPU 中选取 \(m\) 对（即 \(2m\) 台），若总数不足 \(2m\) 台，则选取尽量多对。
2. 对于每一对 CPU，测量它们之间的 Relative Performance Difference(RPD)，并把第𝑖对的 RPD 记为 \(D_i\)。RPD 的计算方法在后面给出。
3. 该组 CPU 的 Sqared Performance Difference (SPD) 由以下公式给出：\[\mathtt{SPD}=\sum_{i}{D_i}^2\]
4. 该组 CPU 通过质检，当且仅当 \(\mathtt{SPD}\le k\) , 其中 \(k\) 是给定常数。

ACM公司生产的 CPU 性能很好，而质检部门制定的标准更是过于严格。通常他们把 \(n\) 台 CPU 作为一整组进行测试，这导致一些性能良好的 CPU 无法通过测试，生产部门对此颇有微词。作为质检部门的领导，小S在不更改质检测试流程的前提下，想出了这样一个主意：如果能够把 \(n\) 台 CPU 恰当地分成连续的若干段，使得每段CPU都能够通过成组测试，就可以解决当下的问题。

现在，小S已经知道了 \(n\) 台各自的性能表现 \(P_1\cdots P_n\)，两台 CPU 的 RPD 被定义为它们性能表现的差的绝对值。请你帮忙计算一下，至少把这些 CPU 分成多少段，才能使得每一段都能通过成组测试。

Input

每个测试点包含多组数据，第一行一个整数 \(t\) 给出数据组数。对于每组数据，第一行三个整数 \(n,m,k\) ，第二行 \(n\) 个整数 \(P_1\cdots P_n\)。

Output

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

Limitations

对于 \(20\%\) 的数据，\(1\le n\le10^2\)。
对于 \(40\%\) 的数据，\(1\le n\le10^3\)。
对于另外 \(10\%\) 的数据，\(k=0\)。
对于另外 \(10\%\) 的数据，\(0\le k\le1\)。
对于另外 \(10\%\) 的数据，\(m=1\)。
对于另外 \(10\%\) 的数据，\(1\le m\le2\)。
对于 \(90\%\) 的数据，\(0\le k\le10^{12}\)。
对于 \(100\%\) 的数据，\(t\le12\), \(1\le n,m\le5\times 10^5\), \(0\le k\le10^{18}\), \(0\le P_i\le2^{20}\)。

Samples

Sample #1

Input

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

Output

2
1

Source

算法竞赛进阶指南 POJ