您是 Codeforces 回合的作者,并准备了您要设置的 $$$n$$$ 问题,问题 $$$i$$$ 有难度 $$$a_i$$$。您将执行以下过程:
- 从列表中删除一些(可能为零)问题;
- 按照您希望的任何顺序重新排列剩余的问题。
当且仅当任何两个连续问题的难度之间的绝对差值最多为 $$$k$$$(小于或等于 $$$k$$$)时,一轮才被视为平衡。
为了使问题的安排达到平衡,您必须消除的最少问题数量是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个正整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) 和 $$$k$$$ ($$$1 \leq k \leq 10^9$$$) - 问题数量以及连续问题之间允许的最大绝对差。
每个测试用例的第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) - 每个问题的难度。
请注意,所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 您必须删除的最小问题数,以便平衡问题的排列。
示例
输入 #1
7 5 1 1 2 4 5 6 1 2 10 8 3 17 3 1 20 12 5 17 12 4 2 2 4 6 8 5 3 2 3 19 10 8 3 4 1 10 5 8 1 8 3 1 4 5 10 7 3
输出 #1
2 0 5 0 3 1 4
注意
对于第一个测试用例,我们可以删除前 $$$2$$$ 问题,并使用难度为 $$$[4, 5, 6]$$$ 的问题构建一个集合,相邻问题之间的难度等于 $$$|5 - 4| = 1 \leq 1$$$ 和 $$$|6 - 5| = 1 \leq 1$$$。
对于第二个测试用例,我们可以采用单个问题并使用难度为 $$$10$$$ 的问题组成一轮。