G. Gruesome Polynomials
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Lieutenant Bigolin is a true mathematical prodigy and cannot comprehend those who don't understand polynomials. He was soon assigned to be the leader of the fifth year students at the Institute of Methodical Extortion, also referred to as IME. In this position, he did something mischievous: he converted every student record into algebraic challenges!

However, you are found to be torando (which in Brazilian military jargon means sleeping, but can also mean something else...) when Captain Icarus Mandrade wakes you up shouting. Since you are torando, you are now assigned to be the leader of the fifth year students and must take into account everything that Bigolin was doing.

You have 4 seconds to hand me a list of every student's aim-correction angle or you'll be toast!, shouted the Captain.

Panicking, you open the only file available (a plain-text note) and find $$$t$$$ monic polynomials written line after line. In an instant, you realize that the real roots of these $$$t$$$ polynomials are precisely every student's aim-correction angle (in degrees). You remember also from the aiming lesson that each angle is in the range $$$[-30^\circ, 30^\circ]$$$ and that no two students' angles were more than $$$0.5^\circ$$$ close.

Figure this out before you are toast!

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the amount of polynomials found in the notepad.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 8)$$$ — the degree of the polynomial.

The second line of each test case contains $$$n + 1$$$ real numbers $$$(a_0, a_1, ..., a_n)$$$ $$$(-10^{17} \leq a_i \leq 10^{17})$$$ — the coefficients of the polynomial from the lowest degree $$$0$$$ to the highest degree $$$n$$$. Each real number will be given up to 8 decimal digits. That is, the polynomial is equal to the sum of $$$a_i \times x^i$$$ for $$$i$$$ from $$$0$$$ to $$$n$$$. It is guaranteed that the roots fall within the range $$$[-30, 30]$$$ and that the roots are at least $$$0.5$$$ apart.

Output

For each test case, output $$$n$$$ sorted real numbers in a single line — the roots of the polynomial. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$, that being if your answer is $$$a$$$ and the jury's is $$$b$$$, then the judge will check if $$$\frac{|a - b|}{max(1, b)} \leq 10^{-6}$$$.

Examples
Input
2
2
-5 -13 40
4
942 -9398 -939 81 8
Output
-0.22660959 0.55160952 
-10.99056762 -10.01322889 0.09925818 10.77953821
Input
2
5
7138.2900 1927.17 -2082.05 -500.245 -3.141592 2.71828
2
-589.241 29.2085 69
Output
-9.25042868 -5.46170789 -1.74924898 1.88924450 15.72786874 
-3.14159149 2.71827978