K. Rainbow Subarray
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

TEN is an exciting push-your-luck and auction board game. Players may push their luck to draw more cards and use currency to buy additional cards in their attempt to build the longest number sequence in each color. Here let's consider a related problem to the game.

Photo by @freethemeeple on Instagram

Given a sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$, we say its continuous subarray $$$a_l, a_{l + 1}, a_{l + 2}, \cdots, a_r$$$ is a rainbow subarray if $$$a_{i + 1} - a_i = 1$$$ for all $$$l \le i \lt r$$$. Specifically, a subarray of length $$$1$$$ is always a rainbow subarray.

You can perform at most $$$k$$$ operations. Each operation allows you to increase or decrease an element in the sequence by one. Calculate the maximum possible length of the longest rainbow subarray after performing the operations.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5 \times 10^5$$$, $$$0 \le k \le 10^{15}$$$) indicating the length of the sequence and the maximum number of operations you can perform.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) indicating the sequence.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$5 \times 10^5$$$.

Output

For each test case output one line containing one integer indicating the maximum possible length of the longest rainbow subarray after performing at most $$$k$$$ operations.

Example
Input
5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3
Output
4
3
5
1
1
Note

For the first sample test case, we can perform $$$4$$$ operations and change the sequence to $$$\{7, 3, 4, 5, 6, 11, 7\}$$$. The longest rainbow subarray is $$$\{3, 4, 5, 6\}$$$, so the answer is $$$4$$$.

For the second sample test case, we cannot perform any operation. The longest rainbow subarray is $$$\{3, 4, 5\}$$$, so the answer is $$$3$$$.

For the third sample test case, we can perform $$$6$$$ operations and change the sequence to $$$\{-1, 0, 1, 2, 3\}$$$. The whole sequence is a rainbow subarray, so the answer is $$$5$$$.