여유로운 집합

Ada와 John은 가장 친한 친구이다. 둘은 지루해졌고, Ada는 John에게 자신을 위해 퍼즐을 풀어 달라고 한다.

집합 $S$은 $S$의 서로 다른 원소로 이루어진 각 쌍의 절댓값 차이가 적어도 $\mathbf{K}$이면 여유롭다고 한다. 즉, $x \ne y$인 모든 $x, y \in S$에 대해 $|x - y| \ge \mathbf{K}$이어야 한다.

Ada에게는 크기가 $\mathbf{N}$인 서로 다른 정수의 목록 $\mathbf{A}$과 정수 $\mathbf{K}$가 있다. 각 $\mathbf{A_i}$에 대해, Ada는 John에게 $\mathbf{A}$의 원소로 구성되고, $\mathbf{A_i}$을 포함하며 여유로운 집합 $S_i$의 최대 크기 $S_i$를 구해 달라고 한다.

참고: 집합 $S_i$은 목록에서 연속한 원소들로 구성될 필요가 없다.

제한

시간 제한: 20초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $-10^9 \le \mathbf{A_i} \le 10^9$. 모든 $i \ne j$에 대해 $\mathbf{A_i} \ne \mathbf{A_j}$.

테스트 세트 1 (결과 공개)

$1 \le \mathbf{N} \le 10$. $1 \le \mathbf{K} \le 100$.

테스트 세트 2 (결과 공개)

$1 \le \mathbf{K} \le 10^9$. 최대 15개의 케이스에 대해: $1 \le \mathbf{N} \le 10^5$. 나머지 케이스에 대해: $1 \le \mathbf{N} \le 10^3$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$와 $\mathbf{K}$가 주어진다. 다음 줄에는 $\mathbf{N}$개의 정수 $\mathbf{A_1} \mathbf{A_2} \dots \mathbf{A_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y_1 ~ y_2 \dots ~ y_\mathbf{N}$을 포함하는 한 줄을 출력한다. 여기서 $x$은 테스트 케이스 번호이며(1부터 시작), $y_i$은 $\mathbf{A_i}$를 포함하며 $\mathbf{A}$의 원소로 구성된 여유로운 집합의 최대 크기이다.

예제 케이스 #1에서 여유로운 집합은 $1$와 $2$를 함께 포함할 수 없으며, $2$와 $3$도 함께 포함할 수 없다. 이는 $S_2 = \{2\}$임을 뜻하며, $S_1 = S_3 = \{1,3\}$를 사용하면 집합의 크기가 최대가 된다.

예제 케이스 #2에서 가능한 최대 크기의 집합은 다음과 같다:

• $S_1 = S_2 = S_3 = S_4 = \{2,7,11,19\}$,

• $S_5 = \{11,19,5\}$, 그리고

• $S_6 = \{7,11,19,3\}$.