Mariano's farm can be viewed as a horizontal line, and at certain positions with integer coordinates, there is a pen that initially contains a single chicken. The chickens have a limited flying capacity and can only fly from one pen to another if the difference in coordinates of the two pens is less than a certain number $$$k$$$. We will say that two chickens are friends if one can fly to where the other is located using as many pens as they want as intermediate points. For example, if the chickens can fly a distance of 2 and we have 3 chickens at positions 1, 2, and 4, the chickens at positions 1 and 4 are friends because the first chicken can go to position 4 passing through position 2. Of course, Mariano wants his chickens to be able to relate to each other, but without causing chaos on the farm. Therefore, he asks you to determine the minimum distance they must be able to fly so that there are at least $$$a$$$ pairs of friends, given $$$a$$$, the number of pairs of chickens he wants to be friends.
The input starts with an integer $$$t$$$, the number of cases. It is followed by $$$t$$$ cases, each starting with two integers $$$n$$$ and $$$a$$$, the number of pens (each with one chicken) and the number of pairs of friend chickens that Mariano wants. Following this are $$$n$$$ integers, $$$x_i$$$, indicating the positions of the chickens. No two pens are at the same point, and it holds that $$$0 \leq x_i \leq 10^9$$$, $$$1 \leq a \leq n(n-1)/2$$$.
Print $$$t$$$ lines, each with a single number, the minimum distance that the chickens must be able to fly in each case.
$$$2 \leq n \leq 10$$$ (10 points)
$$$2 \leq n \leq 1000$$$ and $$$0 \leq x_i \leq 10000$$$ (13 points)
$$$2 \leq n \leq 1000$$$ (23 points)
$$$2 \leq n \leq 10^5$$$ and $$$a=1$$$ (5 points)
$$$2 \leq n \leq 10^5$$$ and $$$a=n(n-1)/2$$$ (8 points)
$$$2 \leq n \leq 10^5$$$ and no additional restrictions (41 points)
2 3 2 1 2 4 3 1 1 2 4
2 1
