B. Vending Machines
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The research facility where you work has a number of rooms and only one straight corridor of length $$$10^8$$$. Each room has one door leading to the corridor.

You are going to install some vending machines on this corridor. For the convenience of the researchers, you want to place them so that every door has at least one vending machine sufficiently close to it. You are given the positions of the doors and the maximum allowed distance from each door to its nearest vending machine. Find the minimum number of vending machines needed to satisfy this condition.

A vending machine may be installed anywhere on the corridor, possibly at the same position as a door or at an end of the corridor. In this problem, the corridor is regarded as a line segment with no width, and doors and vending machines are treated as points on that line segment.

Input

The input contains one or more test cases, each in the following format.

$$$n$$$ $$$d$$$
$$$x_{1}$$$ $$$x_{2}$$$ $$$\cdots$$$ $$$x_{n}$$$

Each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$d,$$$ representing the number of doors and the maximum allowed distance from each door to its nearest vending machine, respectively ($$$1 \le n \le 100$$$, $$$1 \le d \le 10^8$$$). The second line contains the positions of the doors. For each $$$i=1,2,\ldots,n$$$, $$$x_i$$$ is an integer representing the distance from one end of the corridor to the $$$i$$$-th door ($$$0 \le x_1 \lt x_2 \lt \cdots \lt x_n \le 10^8$$$).

The end of the input is indicated by a line containing two zeros. The number of test cases does not exceed $$$100$$$.

Output

For each test case, output the minimum number of vending machines required in a line.

Example
Input
3 5
10 20 40
9 1
0 1 2 3 4 5 6 7 8
2 300
123 724
1 100000000
100000000
0 0
Output
2
3
2
1
Note

In the first test case of Sample Input 1, for example, it is sufficient to install vending machines at positions $$$15$$$ and $$$40$$$.