J. Laser Balancing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a certain laboratory, $$$n$$$ lasers are suspended from the ceiling. Initially, each laser is suspended at a distance of $$$a_i$$$ from the ceiling. All lasers hang in the same plane, and each has its own unique coordinate $$$x_i = i$$$.

At the other end of the room is a screen. All lasers emit light towards the screen, so if $$$2$$$ lasers hang at the same height, the light from the laser with the smaller coordinate does not reach the screen.

You can take any laser and increase its distance from the ceiling by $$$1$$$ no more than $$$k$$$ times. You are interested in determining the maximum number of lasers whose light will be registered by the screen with optimal use of the operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — the total number of lasers and the number of operations, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) separated by spaces — the initial distances of the lasers from the ceiling.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer on a single line — the maximum number of lasers whose light reaches the screen after applying no more than $$$k$$$ operations.

Example
Input
3
4 4
1 2 3 4
4 5
1 1 1 1
9 2
4 3 3 10 5 5 5 99 11
Output
4
3
7
Note

First test case

All lasers are already at different heights, so they do not block each other's light.

Second test case

Initially, all lasers are at the same height, so only the light from the $$$4$$$-th laser reaches the screen.

You can increase the distance for the $$$2$$$-nd laser by $$$1$$$ and the distance for the $$$3$$$-rd laser by $$$2$$$ — in this case, the lasers will be at distances $$$[1, 2, 3, 1]$$$.

A total of $$$3$$$ operations will be performed (out of $$$5$$$ available), and the light from $$$3$$$ lasers reaches the screen.

Note that with the $$$5$$$ available operations, it is impossible to make all $$$4$$$ lasers hang at different heights.

Third test case

One of the lasers at a distance of $$$5$$$ can be moved to $$$1$$$ — in this case, the light from $$$7$$$ different lasers will reach the screen.

Note that the distance from the ceiling cannot be decreased — you cannot move one of the lasers at a distance of $$$3$$$ to $$$1$$$ closer to the ceiling (so that its new distance equals $$$2$$$).