TAP2013F - Flowers of Babylon

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2013 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013-problems.pdf]

In Babylon grow some plants with flowers that are very much appreciated among the inhabitants. Florencio is such an inhabitant of Babylon who has a garden with N plants of these species, and he wants to collect some of their flowers. Because Florencio is quite lazy he does not want to go through a lot of effort to collect the flowers. Therefore, he has decided to walk to some point in his garden, and then with a circular movement of his scythe he shall cut a good amount of plants to later collect their flowers. Florencio is very skillful using the scythe so he will cover with it a perfect circle centered wherever he is standing, which will allow him to cut all the plants lying within this circle, including its border. The higher Florencio has to lift his scythe, the greater the radius of the corresponding circle he will cover with it. Florencio wants to cut at least P plants, but his laziness is such that he wants to do so lifting his scythe as little as possible.

Florencio has managed to get his hands on a satellite image of his garden where all of his plants appear, and he has furthermore managed to get someone to convert this image to a list where each plant is represented by its coordinates in an XY plane. Now he is sitting outside, his scythe in hand, waiting for your team to tell him the minimum radius of a circle that encloses at least P plants.

 

Input

The first line contains a single integer number T, the number of test cases (1 ≤ T ≤ 100).

For each test case, the first line contains two integer numbers N and P, which respectively represent the number of plants that there are in the garden and the minimum number of plants that Florencio wants to cut (1 ≤ P  N  500). Each of the following N lines describes a different plant using two integer numbers X and Y, representing the coordinates of that plant in the XY plane ( X, Y  105). No two plants sit at the same position.

 

Output

For each test case, print a line containing a single rational number representing the minimum radius of a circle enclosing at least P plants. You should print the result using exactly 4 digits after the decimal mark, rounding if necessary (there will be no rounding ties).

 

Example

Input:
2
3 2
10000 10000
10000 9999
9999 10000
2 1
1 1
10000 10000
Output:

0.5000
0.0000 



Added by:Fidel Schaposnik
Date:2013-10-07
Time limit:120s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64