PropBot

You have been selected to write the navigation module for PropBot. Unfortunately, the mechanical engineers left very little freedom of movement, so PropBot can perform only two distinct actions.

• Move forward 10 cm in the direction it currently faces.
• Turn right (clockwise) by 45 degrees.

Each action takes exactly one second.

The module receives two inputs: the Cartesian coordinates of a point on the plane that PropBot wants to get as close to as possible, and the maximum number of seconds it may use to do so. At the start of navigation the robot is at the origin, facing the $+x$ direction.

The number of seconds is an integer between 0 and 24, inclusive. The x and y coordinates of the target point are each real numbers between -100 and 100, inclusive, measured in the same centimeters as the forward step.

The first line of input contains the number of test cases $t$ ($0 < t \le 100$). Each of the following $t$ lines contains three space-separated values: the number of seconds PropBot may use to approach the point, the x-coordinate of the point, and the y-coordinate of the point.

For each test case, print on its own line the distance between the target point and the closest point the robot can reach within the given time. This minimum distance is uniquely determined.

The output must contain at least one digit to the left of the decimal point and exactly six digits to the right. To keep round-off error from affecting the result, the test data is constructed so that the seventh digit to the right of the decimal point of the true answer is never a 4 or a 5.