D. Building A Smooth Playlist
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Nicolas is creating a new playlist with songs from different genres. He has $$$n$$$ different genres, and each genre has $$$c_i$$$ different songs. Each song is in exactly one genre. He wants to add $$$m$$$ songs to the playlist, and they should be chosen from the different genres as evenly as possible so the playlist has a smooth sound.

Formally, given $$$n$$$ genres with $$$c_i$$$ songs each, he wants to choose $$$m$$$ songs without replacement as evenly as possible. What's the minimum difference between the number of songs from the most taken genre and the number of songs from the least taken genre?

Assuming $$$k_i$$$ is the amount of songs he picks from genre $$$i$$$, he wants to minimize:

$$$$$$\max k_i - \min k_i$$$$$$

subject to $$$0 \leq k_i \leq c_i$$$ and $$$\sum k_i = m$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases.

The first line of each test case contains two integers $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the number of genres, and $$$m$$$ ($$$1 \leq m \leq \sum c_i$$$), the number of songs he wants to pick for the playlist.

The second line of each test case contains $$$n$$$ integers $$$c_1,\dots,c_n$$$ ($$$1 \leq c_i \leq 10^9$$$), the number of songs in the $$$i$$$'th genre.

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

Output

Print one integer per test case, the minimum difference of the count of songs between the most and the least taken genre.

Example
Input
2
4 5
1 1 3 3
4 8
3 4 2 5
Output
1
0
Note

In the first test case, Nicolas can pick $$$1$$$ song each from the first two genres, $$$2$$$ songs from the third genre and $$$1$$$ song from the last genre. This will lead to a difference of $$$2 - 1 = 1$$$.

In the second test case, Nicolas can pick $$$2$$$ songs from each genre so there is a maximum difference of $$$0$$$.