P12953 [GCJ Farewell Round #2] Spacious Sets

Ada and John are best friends. Since they are getting bored, Ada asks John to solve a puzzle for her. A set $S$ is considered *spacious* if the absolute difference between each pair of distinct elements of $S$ is at least $\mathbf{K}$, that is, $|x - y| \geq \mathbf{K}$ for all $x, y \in S$, with $x \neq y$. Ada has a list of distinct integers $\mathbf{A}$ of size $\mathbf{N}$, and an integer $\mathbf{K}$. For each $\mathbf{A}_i$, she asks John to find the maximum size of a set $S_i$ made of elements from $\mathbf{A}$, such that $S_i$ contains $\mathbf{A}_i$ and is spacious. Note: The sets $S_i$ do not need to be made of consecutive elements from the list.

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of each test case contains two integers $\mathbf{N}$ and $\mathbf{K}$. The next line contains $\mathbf{N}$ integers $\mathbf{A}_1 \mathbf{A}_2 \ldots \mathbf{A}_{\mathbf{N}}$.

For each test case, output one line containing Case # $x$: $y_1 \ y_2 \ldots \ y_{\mathbf{N}}$, where $x$ is the test case number (starting from 1) and $y_i$ is the maximum size of a spacious set of elements from $\mathbf{A}$ that contains $\mathbf{A}_i$.

**Sample Explanation** In Sample Case #1, a spacious set cannot contain $1$ and $2$, nor it can contain $2$ and $3$. That implies that $S_2 = \{2\}$ and using $S_1 = S_3 = \{1, 3\}$ makes them of maximum size. In Sample Case #2, possible sets of maximum size are: * $S_1 = S_2 = S_3 = S_4 = \{2, 7, 11, 19\}$, * $S_5 = \{11, 19, 5\}$, and * $S_6 = \{7, 11, 19, 3\}$. **Limits** - $1 \leq \mathbf{T} \leq 100$. - $-10^9 \leq \mathbf{A}_i \leq 10^9$, for all $i$. - $\mathbf{A}_i \neq \mathbf{A}_j$, for all $i \neq j$. **Test Set 1 (4 Pts, Visible Verdict)** - $1 \leq \mathbf{N} \leq 10$. - $1 \leq \mathbf{K} \leq 100$. **Test Set 2 (10 Pts, Visible Verdict)** - $1 \leq \mathbf{K} \leq 10^9$. For at most 15 cases: - $1 \leq \mathbf{N} \leq 10^5$. For the remaining cases: - $1 \leq \mathbf{N} \leq 10^3$.