卢克喜欢吃。他面前有$$$n$$$成堆的食物,排成一条直线。第 $$$i$$$ 堆包含 $$$a_i$$$ 单位的食物。
Luke将从第$$$1$$$堆走向第$$$n$$$堆,并且他想吃掉每一堆食物而不走回头路。当卢克到达第 $$$i$$$ 堆时,他可以吃掉那堆当且仅当 $$$|v - a_i| \leq x$$$,其中 $$$x$$$ 是固定整数,$$$v$$$ 是 Luke 的食物亲和力。
Luke开始走路之前,他可以将$$$v$$$设置为任何整数。此外,对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$),卢克可以在吃掉第 $$$i$$$ 堆之前将他的食物亲和力更改为任何整数。
求吃完每一堆食物所需的最少变化次数。
请注意,$$$v$$$ 的初始选择不被视为更改。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
对于每个测试用例,第一行包含两个整数,$$$n, x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x \leq 10^9$$$) — 堆的数量,以及堆的大小与卢克的食物亲和力之间的最大差异,这样卢克就可以吃掉这堆。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出一个整数,这是所需的最小更改数。
示例
输入 #1
7 5 3 3 8 5 6 7 5 3 3 10 9 8 7 12 8 25 3 3 17 8 6 1 16 15 25 17 23 10 2 1 2 3 4 5 6 7 8 9 10 8 2 2 4 6 8 6 4 12 14 8 2 2 7 8 9 6 13 21 28 15 5 11 4 13 23 7 10 5 21 20 11 17 5 29 16 11
输出 #1
0 1 2 1 2 4 6
注意
在第一个测试用例中,Luke 可以在开始行走之前将 $$$v$$$ 设置为 $$$5$$$。而且他可以直接走去吃掉每一堆食物,而不会改变$$$v$$$。
在第二个测试用例中,Luke 可以在开始行走之前将 $$$v$$$ 设置为 $$$3$$$。在吃第二堆之前,他可以将 $$$v$$$ 更改为 $$$10$$$。之后,他可以直接走去吃剩下的食物,而无需改变$$$v$$$。
在第四个测试用例中,Luke 在开始行走之前可以将 $$$v$$$ 设置为 $$$3$$$。在吃第六堆之前,他可以将 $$$v$$$ 更改为 $$$8$$$。之后,他可以直接走去吃剩下的食物,而无需改变$$$v$$$。
在第五个测试用例中,Luke 在开始行走之前可以将 $$$v$$$ 设置为 $$$4$$$。在吃第四堆之前,他可以将 $$$v$$$ 更改为 $$$6$$$。然后他可以在吃第七堆之前将 $$$v$$$ 更改为 $$$12$$$。之后,他可以直接走去吃剩下的食物,而无需改变$$$v$$$。