Page not loading? Try clicking here.
Placeholder

#10455

Spacious Sets 20s 2048MB

Problems

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| \ge \mathbf{K} for all x, y \in S, with x \ne 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.


Input

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} \dots \mathbf{A_N}.


Output

For each test case, output one line containing Case #x: y_1 ~ y_2 \dots ~ 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}.


Example 

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
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\}.

Source

GCJ 2023b C

You must sign in to write code.