Yesterday I had a Samsung test. There a question which I wasn't able to solve. Can someone please tell me how to solve this. (Sorry for my bad English and also I can't provide the link for exact question).

You have given n student. Each student contains a number ( which need not be unique). Students are standing in a queue. You have also given an integer k. You can remove the students such that the number contains by students follow this rule:

• $$$ arr[i-1]+k=arr[i]=arr[i+1]-k $$$.(All three students will be removed from the queue).

You have to remove these students such that the minimum number of student will be remaining at the end.

Constraints:

• $$$ 1<=t<=20. $$$

• $$$ 3<=n<=100. $$$

• $$$ 1<=k<=10^6 $$$.

• $$$ 1<=arr[i]<=10^6 $$$.

Input :

2

6 1

3 4 5 6 7 5

5 1

1 2 3 4 5

Output:

0

2

Explanation: In the first test case, If we remove 5 6 7 then the remaining array will be 3 4 5. Now again I can remove these students. So the minimum number of student remaining will be 0.

In the second test case, we can't remove more than three students from the queue. So the remaining number of students will be 2.