Bessie at HMC

During the Fall of 2011, all of the high-school-senior cows are making their visits to various colleges and universities. When they arrive at Harvey Mudd, the cows are most interested in the availability of coffee throughout the campus.

Dean Jacobsen, hoping to lure the whole herd to HMC, has offered to scuttle the new academic building project and, in its place, to build coffee shops across campus for the cows. Specifically, Dean Jakes would like to know where he should place these cafes -- and how much moovement will still be required for the cows to get to their java.

The cows enjoy herding and they know they will create a number of "cow-preferred hang outs" at HMC. However, the exact locations of those hang-outs will depend on factors like the weather and their proximity to CS classes. Thus, for a given set of "preferred hang outs" and a given number of available coffee kiosks, Jakes would like to know how well-coffee'd the cows will be.

The plan is to place the available kiosks so that the maximum distance between any hang-out spot and its nearest kiosk is as small as possible. For the purposes of the cows' caffeination, HMC's campus can be considered a one-dimensional strip, whose origin is the western edge, Olin, where the CS department is located. Each location to the east of Olin is measured in millimeters, and only integer locations are considered.

Input Specification

The first line of input contains an integer specifying the number of test cases to follow. Then, the first line of each test case contains two positive integers n, the number of kiosks that Dean Jakes can build, and m, the number of the cows' hang-out spots across campus. The following m lines contain the locations of those spots, all integers, with one number per line. There will be no more than 100,000 spots across campus and their locations will be no larger than 1,000,000 mm, since the cows can't imagine being any further than that from Olin.

Sample Input

2 3

This indicates 1 test case, two coffee kiosks, and 3 hang-out locations at 1mm, 3mm, and 10mm east of Olin, respectively. The cows move slowly, so they like their herding spots close together!

Output Specification

For each test case, output a line containing one number, the maximum distance between any hang-out spot and the cofee kiosk nearest to it. Round the number to the nearest tenth of a millimeter, and output it with exactly one digit after the decimal point.

Output for Sample Input


Explanation of sample output

Dean Jakes can build the two kiosks at location 2 and location 10. In this case the greatest coffee-distance would be 1.0, namely the distance from 1 to 2 (and it's also the distance from 3 to 2).

Hint: try binary search!