You must solve N problems with the numbers 1..N. The problems are listed in order of increasing complexity, with the ith problem having an estimated difficulty level of i. Each issue has also been given a grade of vi by you. Comparable vi values lead to similar types of issues. You will pick a portion of the issues and address them each day. You've made the decision that each issue you solve on that day should be more difficult than the one before it. It will also be less monotonous if the vi ratings of the subsequent problems you answer differ by at least K. What is the shortest amount of time that you can fix every issue? Input Format The first line contains the number of test cases T. T test cases follow. Each case contains an integer N and K on the first line, followed by integers v1,...,vn on the second line. Constraints 1 <= T <= 100 1 <= N <= 300 1 <= vi <= 1000 1 <= K <= 1000 Output Format Output T lines, one for each test case, containing the minimum number of days in which all problems can be solved. Sample Input 2 3 2 5 4 7 5 1 5 3 4 5 6 Sample Output 2 1 Explanation For the first example, you can solve the problems with rating 5 and 7 on the first day and the problem with rating 4 on the next day. Note that the problems with rating 5 and 4 cannot be completed consecutively because the ratings should differ by at least K (which is 2). Also, the problems cannot be completed in order 5,7,4 in one day because the problems solved on a day should be in increasing difficulty level. For the second example, all problems can be solved on the same day.
You must solve N problems with the numbers 1..N. The problems are listed in order of increasing complexity, with the ith problem having an estimated difficulty level of i. Each issue has also been given a grade of vi by you. Comparable vi values lead to similar types of issues. You will pick a portion of the issues and address them each day. You've made the decision that each issue you solve on that day should be more difficult than the one before it. It will also be less monotonous if the vi ratings of the subsequent problems you answer differ by at least K. What is the shortest amount of time that you can fix every issue?
Input Format
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N and K on the first line, followed by integers v1,...,vn on the second line.
Constraints
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000
Output Format
Output T lines, one for each test case, containing the minimum number of days in which all problems can be solved.
Sample Input
2
3 2
5 4 7
5 1
5 3 4 5 6
Sample Output
2
1
Explanation
For the first example, you can solve the problems with rating 5 and 7 on the first day and the problem with rating 4 on the next day. Note that the problems with rating 5 and 4 cannot be completed consecutively because the ratings should differ by at least K (which is 2). Also, the problems cannot be completed in order 5,7,4 in one day because the problems solved on a day should be in increasing difficulty level.
For the second example, all problems can be solved on the same day.
Step by step
Solved in 4 steps with 2 images
