F. Regular Covering
time limit per test
8 s
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ points $$$a_1,a_2,\dots,a_n$$$ inside the cartesian grid, where for each integer $$$1 \leq i \leq n$$$, $$$a_i$$$ is located at the coordinate $$$(x_i,y_i)$$$. No two points share the same coordinates.

You want to cover all of the points with a regular polygon which has $$$m$$$ sides. However, you have to place the center of the polygon at the coordinate $$$(0,0)$$$. You can place the polygon at any rotational orientation.

Define the size of the regular polygon as the distance between the center point of the polygon (or in this case, the coordinate $$$(0,0)$$$) and one of the vertices of the polygon. Find the minimum size of the polygon such that there exist a way to covers all $$$n$$$ points with it.

Input

The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — the number of test cases.

The first line of each test cases contains two integers $$$n,m$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 3 \leq m \leq 3000$$$) — the number of points and the number of sides on the polygon.

For the next $$$n$$$ lines of each test cases, each line contains two integers $$$x_i,y_i$$$ ($$$-2 \cdot 10^4 \leq x_i,y_i \leq 2 \cdot 10^4$$$) — the coordinate of $$$a_i$$$.

It is guaranteed that $$$(x_i,y_i) \neq (x_j,y_j)$$$ for each $$$1 \leq i \lt j \leq n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single real number — the minimum size of the polygon.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$ — formally, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, your answer will be accepted if $$$\frac{|a−b|}{\max(1,b)} \leq 10^{−9}$$$.

Example
Input
3
2 3
0 4
3 -2
5 4
0 0
0 1
1 0
0 -1
-1 0
3 5
8 1
-5 5
-4 -7
Output
4
1
8.844723953
Note

For the first test case, the points and the polygon looks like this: If the size of the polygon is less than $$$4$$$, the point $$$a_1$$$ cannot be covered by the polygon no matter how the polygon is placed. Thus, the minimum size of the polygon is $$$4$$$.

For the second test case, the points and the polygon looks like this: