题目描述

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$.

2
3 2
1 2 3
6 4
2 7 11 19 5 3

Case #1: 2 1 2
Case #2: 4 4 4 4 3 4

提示

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$.