题目描述

给定一个整数 $\red{M}$，对于任意一个整数集合 $\red{S}$，定义“校验值”如下:

从集合 $\red{S}$ 中取出 $\red{M}$ 对数(即 $\red{2*M}$ 个数，不能重复使用集合中的数，如果 $\red{S}$ 中的整数不够 $\red{M}$ 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 $\red{S}$ 的“校验值”。

现在给定一个长度为 $\red{N}$ 的数列 $\red{A}$ 以及一个整数 $\red{T}$。

我们要把 $\red{A}$ 分成若干段，使得每一段的“校验值”都不超过 $\red{T}$。

求最少需要分成几段。

输入格式

第一行输入整数 $\red{K}$，代表有 $\red{K}$ 组测试数据。

对于每组测试数据，第一行包含三个整数 $\red{N,M,T}$ 。

第二行包含 $\red{N}$ 个整数，表示数列$\red{A_1 ,A_2 …A_N}$ 。

输出格式

对于每组测试数据，输出其答案，每个答案占一行。

样例

输入数据

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

输出数据

2
1

提示

$\red{1≤K≤12,}$

$\red{1≤N,M≤500000,}$

$\red{0≤T≤10^{18} ,}$

$\red{0≤A_i ≤2^{20} }$