High School Programming League Problems Archive

Given a circle and a line segment compute their point of intersection. You can assume that one of the endpoints of the line segment belongs to the interior of the circle, while the other to the exterior.

Input

First t < 1000, the number of test cases. In each of the following t lines, 7 integers: -1000 <= x, y <= 1000, where x and y are the circle center coordinates and 0 < r <= 1000 the radius of the circle; -1000 <= x₁, y₁, x₂, y₂ <= 1000, where x_i, y_i are the coordinates of the endpoints of the line segment.

Output

For each test case print the intersection point coordinates with two digits of precision.

Example

Input:
2
0 0 1 0 0 0 2
10 10 10 15 10 25 10

Output:
0.00 1.00
20.00 10.00 

Scoring

By solving this problem you score 10 points.