A116097.颗秒

---

题目描述

小W 来到了无畏契约的「试炼大厅」，「试炼大厅」里面有一个靶场。

靶场可以看作一个圆，这个圆被均分为 $c$ 份，对应了 $c$ 个方向，按照顺序编号为 $0\sim c-1$。小W 站在这个靶场的中心，他不会移动，只会转动方向。

初始时（第 $0$ 秒），小W 面向 $0$ 号方向，每次训练 小W 会打 $n$ 个靶子。第 $i$ 个靶子会在第 $i$ 秒出现在第 $a_i$ 个方向$(1\le i \le n)$。

由于需要模拟实战效果，很显然的，只有在靶子出现的那一瞬间小W 击中了靶子，才能够认为 小W 击中了靶子。

小W 用的是笨重的大狙，所以他每秒钟最多只能转动 $s$ 个方向，也即往左边转至多 $s$ 个方向，或者往右边转至多 $s$ 个方向，或者选择不转动。

现在 小W 想问你，在最优的情况下，他最多能击中多少个靶子，小W是神枪手，所以他只要面向靶子就一定可以击中。

本题一个测试点内有多组测试数据。

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行输入三个正整数 $n,c,s$，含义见上。

• 第二行输入 $n$ 个整数 $a_i$，含义见上。

输出共 $T$ 行，对于每组测试数据，输出一行一个整数表示最多能击中的靶子数量。

对于第一组测试数据，以下是一种可能的转动方案：

• 第 $0$ 秒，此时没有靶子，转动到 $5$ 方向。
• 第 $1$ 秒，靶子在方向 $0$，小W 在方向 $5$，未命中。转动到 $4$ 方向。
• 第 $2$ 秒，靶子在方向 $4$，小W 在方向 $4$，命中。转动到 $3$ 方向。
• 第 $3$ 秒，靶子在方向 $3$，小W 在方向 $3$，命中。转动到 $4$ 方向。
• 第 $4$ 秒，靶子在方向 $0$，小W 在方向 $4$，未命中。不转动。
• 第 $5$ 秒，靶子在方向 $4$，小W 在方向 $4$，命中。结束。

最终击中了 $3$ 个靶子，你也可以选择在第 $3$ 秒不转动，在第 $4$ 秒转动到 $4$ 方向。可以证明这是最优的打靶方式。

数据范围

对于 $100\%$ 的数据，$1\le T \le 10,1\le n \le 2\times 10^3,1\le s<c\le 10^9,0\le a_i <c$。

测试点编号	特殊性质
$1\sim 3$	$\tt{A}$
$4\sim 10$	$\tt{-}$

特殊性质 $\tt{A}:$ $n\le 10,s=1$。