附加文件

问题描述

共 N 个球迷要一起坐车去看球，他们已经排成了一列队伍。我们要让他们分乘若干辆巴士。同一辆巴士上的球迷必须在原队伍中是连续的。

每个球迷对球赛都有一定的激情值 Ai。为了防止他们过于激情引发冲突，规定坐在同一辆巴士上的球迷必须满足以下条件：

• 从该巴士上任意选出 2×M 个球迷并任意配成 M 对（若巴士上的球迷不足 M 对，则选出到最大配对数为止），使得在任意一种选配方案中，“每对球迷的激情值的差的平方和”不能超过一个给定值 K。

问要将这 N 个球迷全部送至球场，至少需要多少辆巴士？

输入格式

第一行输入整数 T，代表有 T 组测试数据。

对于每组测试数据：

• 第一行：三个整数 N, M, K

• 第二行： N 个整数，表示 Ai

输出格式

每组测试数据的答案占一行。

样例输入

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

样例输出

2
1

数据范围与约定

$T ≤ 12， 1 ≤ N, M ≤ 5×10^5， 0 ≤ K ≤ 10^{18}， 0 ≤ A_i ≤ 2^{20}$