H. Horizon Scanning
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
Cold joke: Radar is a palindrome.

Explanation: It's actually cold knowledge, not a cold joke. The confusion between these concepts is what makes it funny.

—Soy-chicken

Hana recently needs to develop a radar system to monitor abnormal activities across the archipelago she manages.

There are $$$n$$$ islands in the ocean, and the $$$i$$$-th island is located at coordinates $$$(x_i, y_i)$$$, which can be treated as a point on the plane. Assume the radar has a scanning angle range of $$$\alpha$$$. When the radar is rotated to an angle $$$\theta$$$, it can monitor all the islands located within the angular range $$$[\theta - \frac{\alpha}{2}, \theta + \frac{\alpha}{2}]$$$.

Hana is currently low on funds, so she wants to minimize the cost of building the radar. She wants to know, when the radar is placed at the origin $$$(0,0)$$$, what the minimum scanning angle $$$\alpha$$$ should be to ensure that for any angle $$$\theta$$$, the radar can monitor at least $$$k$$$ islands.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of each test case follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2 \times 10^5$$$), representing the total number of islands and the minimum number of islands the radar must monitor at any given time.

The next $$$n$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$|x_i|, |y_i| \leq 10^9$$$), representing the position of an island. It is guaranteed that the coordinates of any two islands are different and none of them are located at the origin.

For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single decimal fraction representing the minimum radar scanning angle in radians.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \leq 10^{-6}$$$.

Example
Input
5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1
Output
6.2831853072
1.5707963268
5.4977871438
3.1415926546
3.1415926536
Note

For the first test case in the example, there is only one island on the plane at $$$(0,1)$$$. To ensure that at least one island is always within range, the radar's monitoring range must be set to $$$360^{\circ}$$$, which is $$$2 \pi$$$ in radians.

For the second test case in the example, there are $$$8$$$ islands on the plane, with each pair of islands separated by $$$45^{\circ}$$$. If the radar's range is less than $$$90^{\circ}$$$, it would only be able to monitor one island when one of its boundaries just moves past an island (as shown on the left of the illustration). Therefore, the minimum radar range needed is $$$90^{\circ}$$$, ensuring that at least two islands are always within range.

Example $$$2$$$ Illustration