C. Variety Hater
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Yazan has an array $$$a$$$ consisting of $$$n$$$ integers.

Yazan can perform the following operation at most $$$k$$$ times:

  • Choose an index $$$i \: (1 \le i \le n)$$$ and either increase $$$a_i$$$ by one or decrease it by one. In other words, either apply $$$a_i:=a_i-1$$$ or $$$a_i:=a_i+1$$$.

Yazan hates variety, so he wants to minimize the number of distinct elements in the array. Can you help him find the minimum number of distinct elements he can have after performing no more than $$$k$$$ operations optimally?

Input

The first line contains one integer $$$t \: (1 \le t \le 100)$$$ — the number of test cases.

The first line of each testcase contains two integers $$$n$$$ and $$$k \: (1 \le n \le 300 , \: 0 \le k \le 10^{12})$$$ — the number of elements and the number of available operations.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n \: (1 \le a_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$300$$$.

Output

For each test case, output the minimum number of distinct elements Yazan can have after performing no more than $$$k$$$ operations.

Example
Input
2
5 1
1 1 1 1 1
5 1
4 4 2 1 4
Output
1
2