Aggressive Cows

Farmer John wishes to place c cows in n stalls such that the minimum distance between any two cows is maximized. The stalls are located on a straight line with given integer positions. Your task is to determine the largest minimum distance d possible between any two cows when they are optimally placed.

More formally, given a sorted list of stall positions \(x_0, x_1, \ldots, x_{n-1}\), you must find the maximum integer \(d\) such that it is feasible to place c cows in these stalls with the condition that for any two cows placed at positions \(x_i\) and \(x_j\) (with \(i < j\)), it holds that \(x_j - x_i \ge d\).

A common approach to this problem is to use binary search to decide the maximum value of d by checking whether a given d can be achieved using a greedy placement strategy.

inputFormat

The first line contains an integer T representing the number of queries. For each query:

• The first line contains two space-separated integers n and c, where n is the number of stalls and c is the number of cows.
• The second line contains n space-separated integers representing the positions of the stalls.

All input is read from standard input (stdin). It is guaranteed that for each query the positions may be provided in an arbitrary order.

outputFormat

For each query, output one line containing a single integer, the largest minimum distance possible between any two cows when they are optimally placed. All output should be written to standard output (stdout).## sample

1
5 3
1 2 8 4 9

3