Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1 s 空间限制:256 MB

#12846. Genius ACM

统计

题目描述

高级CPU制造商(ACM)是世界上最好的CPU制造商之一。每天,他们制造n个CPU芯片,并将其销往世界各地。
正如你所知,每一批CPU芯片都必须通过质量控制部门的质量测试才能出售。测试程序如下:
1) 从一批芯片中随机挑选m对CPU芯片(如果该批芯片中的CPU芯片少于2m,则挑选尽可能多的对。)
2) 对于每一对,测量两个CPU芯片之间的相对性能差异(RPD)。设Di为第i对的RPD,期望RPD尽可能大。
3) 根据以下公式计算该批次的Sqared性能差异(SPD):
    SPD=∑Di^2
    如果一个批次中只有1个CPU,则该批次的SPD为0。
4) 当且仅当SPD≤k时,芯片批次通过测试,其中k是预设常数。

通常,他们每天将所有n个CPU芯片作为一批发送到QC部门。作为世界上最好的CPU制造商之一,ACM从未通不过测试。然而,随着CPU性能的不断提高,他们发现自己正处于危险之中!
当然,他们不想冒任何风险。因此,他们决定将n个芯片分为几个批次,以确保所有芯片都能通过测试。更重要的是,每一批都应该是其生产的连续子序列,否则QC部门会注意到他们在作弊。质量测试需要时间和金钱,所以他们希望尽量减少批次数量。
给定从P1到Pn,n个芯片的绝对性能,您的任务是确定最小批次数,以确保所有芯片都通过测试。两个CPU芯片的RPD等于它们的绝对性能的差异。

输入格式

第一行包含一个整数T,表示测试用例的数量。
在每个测试用例中,第一行包含三个整数n,m,k。
第二行包含n个整数,表示n个芯片的绝对性能。
T≤12
1≤n,m≤5×10^5
0≤k≤10^18
0≤Pi≤2^20

输出格式

对于每个测试用例,将答案打印在一行中。

样例数据

input

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

output

2
1