Assignment
Description:
Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.
Input:
In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means maximum difference between abilities of staff in a group is less than k. second line contains integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate i-th staff’s ability.
Output:
For each test，output the number of groups.
Sample Input:
2 4 2 3 1 2 4 10 5 0 3 4 5 2 1 6 7 8 9
Sample Output:
5 28
Hint:
First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]
Source:
Submit