[Solution] Luke is a foodie Codeforces Solution

B. Luke is a foodie

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Luke likes to eat. There are n$n$ piles of food aligned in a straight line in front of him. The i$i$-th pile contains ai$a_i$ units of food.

Luke will walk from the 1$1$-st pile towards the n$n$-th pile, and he wants to eat every pile of food without walking back. When Luke reaches the i$i$-th pile, he can eat that pile if and only if |v−ai|≤x$|v-a_i|\le x$, where x$x$ is a fixed integer, and v$v$ is Luke's food affinity.

Before Luke starts to walk, he can set v$v$ to any integer. Also, for each i$i$ (1≤i≤n$1\le i\le n$), Luke can change his food affinity to any integer before he eats the i$i$-th pile.

Find the minimum number of changes needed to eat every pile of food.

• of 

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Note that the initial choice for v$v$ is not considered as a change.

Input

The input consists of multiple test cases. The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases. The description of test cases follows.

For each test case, the first line contains two integers, n,x$n,x$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤x≤109$1\le x\le {10}^9$) — the number of piles, and the maximum difference between the size of a pile and Luke's food affinity, such that Luke can eat the pile.

The second line contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$).

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output an integer on a separate line, which is the minimum number of changes needed.