题目内容

给定$n$个非负整数$a_1,a_2,\dots,a_n$，你可以在分组前对这些数进行任意重排。

你需要把所有数划分到若干个桶，每个桶内包含若干个数，设某个桶内共有$t$个数，最小值为$m$，则该桶必须满足：

$1 \leq t \leq L$

$M - m \leq D + E \times (t - 1)$

每个数必须且只能属于一个桶，桶与桶之间互不相交，且并集为全部$n$个数，你的目标是使桶的数量尽可能少，请输出最少桶数。

输入描述

每个测试文件包含多组测试数据，第一行输入一个整数 $T(1 \leq T \leq 10^5)$ 表示数据组数，每组测试数据描述如下：

第一行输入四个整数 $n, D, E, L(1 \leq n \leq 2 \times 10^5, 0 \leq D, E \leq 10^9, 1 \leq L \leq n)$。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n(0 \leq a_i \leq 10^9)$。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示最少需要多少个桶。

补充说明

样例1

输入

2
7 3 1 3
1 2 3 7 8 10 10
7 0 0 5
5 5 5 6 6 6 6

输出

3
2

说明

第一组数据的一个最优划分为$\left[1,2,3\right], \left[7,8,10\right], \left[10\right]$，因此答案为$3$。 第二组数据中由于$D = 0, E = 0$，同一桶内必须全部相等，最少需要$2$个桶。