panda-and-agham

One day Panda with his best friend Agham, set on a very long journey in Cartesian plane. They begin their journey at origin and started moving towards positive x direction. Along the way there are 'n' (n ≥ 2) hotels (relaxing points) in which they can relax, when they are in any hotel, they are said to be in relaxing state. And between any two consecutive relaxing points they are said to be in active state. They have decided that they will have exactly 'k' relaxing states in their entire journey and they wanted to travel in a way, such that, the minimum distance between any two relaxing points is as large as possible. Find the largest minimum distance.

INPUT: 
First line of input contains T the number of test cases.
First line of each test case contains two integers 'n' and 'k' respectively.
Next 'n' lines contains an integer 'q' denoting the position (x co-ordinate) of relaxing points.

OUTPUT:
For each test case output the answer in a new line.   

CONSTRAINTS: 
2< N < 100000    
2< K <100000    
1< points <100000    

SAMPLE INPUT
1
4 2
1
5
10
3

SAMPLE OUTPUT
9

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: