ADOMINO  Arranging Dominoes
Dominoes have long entertained both game enthusiasts and programmers for quite some time. Many games can be played with dominoes, including multiplayer and single player games. Hari Khan has come up with a single player game. He takes N boxes and arranges them in a row at positions N_{1}, N_{2} ... N_{N}. Now he has to place D dominoes (D <= N) in the boxes such that the minimum distance between any two filled boxes is maximized.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
The first line of each test case consists of two integers, N <= 100000 and D <= N, separated by a single space.
N lines follow, each containing a single integer N_{i} <= 1000000000, indicating the location of the i^{th} box.
Output
For each test case, output a single line containing a single integer denoting the largest minimum distance achievable between any two boxes with dominoes.
Example
Input: 1 5 3 1 2 3 4 5 Output: 2
hide comments
CoNtRaDiCtIoN:
20150415 12:25:38
remember two boxes can be at same position !! 

YatsukoYin:
20110124 10:11:09
? <= t <= ? 

(^^,):
20091230 12:24:15
Same Problems: AGGRCOW 
Added by:  Matthew Reeder 
Date:  20061029 
Time limit:  1s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  AlKhawarizm 2006 