Log Jumping

Time limit1sMemory limit128 MB

Summary

Find the largest set of equal-length logs that can be visited in a closed tour where jumps are allowed between logs whose segments share a point.

Level: Medium7 of 10
Topics: Intervals, Sorting, Graph
Solved: No attempts yet

Statement

The villagers keep a set of exercise facilities in the forest behind our village. One of them is made of many logs laid out along a straight trail. Every log has the same length and lies parallel to the trail.

"Log jumping" is a well-known game played there. It is a test of concentration whose goal is to step on as many logs as possible under the rules below.

Choose any log and stand on it. Standing on a log counts as visiting it, and you may walk freely along the log you are currently on.
Choose a log you have not visited yet and jump onto it. Every jump must be made in the direction perpendicular to the logs. Repeat this step as many times as you like.
The last log you land on must be the log you started from. Except for that first-and-last log, each log may be visited at most once. The game ends as soon as you return to the starting log.

For example, suppose there are eight logs of length $5$ , numbered $1$ to $8$ , as in the figure below. Starting on log $2$ you may jump to log $4$ , then log $7$ , log $8$ , log $5$ , and finally back to log $2$ , visiting five logs in total. No route of this kind visits more than five logs, so the maximum here is five.

Given the length of the logs and the position of each log, help Ha-Jin find the largest number of logs she can visit. Two logs are reachable from each other whenever the horizontal segments they occupy share at least one point. In particular, if the right end of one log has the same coordinate as the left end of another, you may jump between the two in either direction. In the figure, for instance, you may jump between log $1$ and log $4$ .

Input

The input is read from standard input. The first line contains the number of test cases $T$ . Each test case consists of two lines. The first line has two integers $n$ and $k$ , the number of logs and their common length ( $1 \le n \le 5000$ , $1 \le k \le 100000$ ). The second line has $n$ integers $x_1, x_2, \ldots, x_n$ separated by single spaces, where $x_i$ is the x-coordinate of the left end of the $i$ -th log ( $-1000000 \le x_i \le 1000000$ ). Each log therefore occupies the segment from $x_i$ to $x_i + k$ .

Output

Write to standard output. For each test case, print a single line containing the maximum number of logs that can be visited.

Examples6

Example 1

Input

4
8 5
-4 4 -5 1 7 -3 4 7
4 5
-5 -4 -3 1
2 10
-1 5
2 3
-1 5

Expected output

Example 2
Input
```
1
1 5
0
```
Expected output
```
1
```
Example 3
Input
```
1
2 5
0 5
```
Expected output
```
2
```
Example 4
Input
```
1
2 5
0 6
```
Expected output
```
1
```
Example 5
Input
```
1
6 100
0 10 20 30 40 50
```
Expected output
```
6
```
Example 6
Input
```
1
5 3
0 3 6 9 12
```
Expected output
```
2
```