CF1238B Kill 'Em All

Ivan 正在玩一款名为 Heretic 的老式动作游戏。他卡在了游戏的最后几个关卡之一，需要你的帮助来消灭怪物。 关卡的主要部分是一个巨大的走廊（如此狭长，以至于可以用一条无限坐标轴来表示）。走廊被分为两部分，假设 $x=0$ 是这两部分的分界点。 走廊的右侧部分充满了 $n$ 只怪物——每只怪物的初始坐标为 $x_i$（由于所有怪物都在右侧部分，所以每个 $x_i$ 都是正数）。 走廊的左侧部分布满了粉碎陷阱。如果某只怪物进入走廊的左侧或原点（即其当前位置小于等于 $0$），它会被陷阱瞬间杀死。 Ivan 用来消灭怪物的主要武器是 Phoenix Rod。它可以发射一枚导弹，导弹在撞击时爆炸，炸死所有被波及的怪物，并将其他怪物从爆炸中心推开。具体来说，假设 Ivan 将导弹发射到 $c$ 点爆炸，则每只怪物要么被炸死，要么被推开。设某只怪物当前位置为 $y$，则： - 如果 $c = y$，该怪物被炸死； - 如果 $y < c$，该怪物会被向左推 $r$ 个单位，当前位置变为 $y - r$； - 如果 $y > c$，该怪物会被向右推 $r$ 个单位，当前位置变为 $y + r$。 Ivan 消灭怪物的过程如下：选择某个整数点 $d$ 并向该点发射导弹，等待爆炸以及所有被推到走廊左侧的怪物被陷阱杀死后，如果还有怪物存活，则再选择一个整数点（可以与之前用过的点相同）发射导弹，如此反复。 请你计算，Ivan 至少需要发射多少次导弹才能消灭所有怪物？你可以假设每次发射 Phoenix Rod 时，Ivan 都会选择最优的爆炸点。 你需要回答 $q$ 个独立的询问。

第一行包含一个整数 $q$（$1 \le q \le 10^5$），表示询问的数量。 每个询问的第一行包含两个整数 $n$ 和 $r$（$1 \le n, r \le 10^5$），分别表示怪物的数量和怪物被爆炸推开的距离。 每个询问的第二行包含 $n$ 个整数 $x_i$（$1 \le x_i \le 10^5$），表示每只怪物的初始位置。 保证所有询问中 $n$ 的总和不超过 $10^5$。

对于每个询问，输出一个整数，表示消灭所有怪物所需的最少导弹发射次数。

在第一个测试用例中，Ivan 的操作如下： - 选择点 $3$，第一只怪物被推到 $-1$ 处被陷阱杀死，第二只怪物被爆炸炸死，第三只怪物被推到 $7$ 处； - 选择点 $7$，第三只怪物被爆炸炸死。 在第二个测试用例中，Ivan 的操作如下： - 选择点 $5$，第一只和第四只怪物被爆炸炸死，第二只怪物被推到 $1$，第三只怪物被推到 $2$； - 选择点 $2$，第一只怪物被推到 $0$ 处被陷阱杀死，第二只怪物被爆炸炸死。 由 ChatGPT 4.1 翻译