题目描述

题目大意

Ethan 经营一个疫苗接种站，帮助人们抵御季节性流感。他分析历史数据，以便开发出最佳的疫苗使用策略。

假设有 $n$ 个病人在特定的一天来到诊所，第 $i$ 个病人在时刻 $t_i$ 来。我们知道这些病人中的每一个都可以被要求等待不超过 $w$ 个时间点。这意味着第 $i$ 个病人可以在时刻 $t_i,t_i+1,…,t_i+w$ 接种疫苗。

疫苗以包装形式出现，每个包装包含 $k$ 剂量。每个病人需要恰好一剂量。包装是存放在一个特殊冰箱里的。如果一个包装被取出并打开，它便不能再放回去。疫苗在冰箱外的寿命为 $d$ 个时间点。因此，如果此包装是在时刻 $x$ 被取出且打开，其剂量可用于在时刻 $x,x+1,…,x+d$ 接种疫苗。在时刻 $x+d+1$，这个包装剩余的未使用剂量全部被扔掉。

假设接种站有足够的工作人员在任意时刻进行任意数量的操作。那么接种所有 $n$ 个病人所需的最少疫苗包装数是多少？

输入格式

第一行是测试用例数 $t$ $(1≤t≤10^4)$。随后是 $t$ 组测试用例的描述。

每个测试用例的第一行包含四个整数 $n$、$k$、$d$ 和 $w$（$1≤n,k≤2⋅10^5，0≤d，w≤10^6$）。它们分别是病人的数量，每个疫苗包装的剂量数，疫苗可在冰箱外存活的时间数以及病人可以等待的时间数。

每个测试用例的第二行包含一个非降序列 $t_1,t_2,…,t_n$（$0≤t_1≤t_2≤⋯≤t_n≤10^6$）。这个序列的第 $i$ 个元素是第 $i$ 个病人来接种疫苗的时刻。

保证所有测试用例中的 $n$ 的总和不超过 $2⋅10^5$。

输出格式

输出一个整数，表示接种所有病人所需的最少疫苗包装数。

Translate by

样例

5
6 3 5 3
1 2 3 10 11 18
6 4 0 0
3 3 3 3 3 4
9 10 2 2
0 1 2 3 4 5 6 7 8
3 10 3 6
10 20 30
5 5 4 4
0 2 4 6 8

2
3
2
3
1