Konajya is learning how to factor polynomials. Her homework assignment consists of $N$ polynomials which she must factor. The $i$-th polynomial has degree $D_i$. Each polynomial is described by a sequence of $D_i+1$ integers which are the coefficients of the polynomial (i.e. $x^2+3x+9$ would be given in the format of 1 3 9). Luckily, you know that each polynomial only has real integer roots. Because she is too lazy to factor them by herself, she decided to give this problem to you, so you can do it for her!

Constraints

$1\le N\le 10000$
$2\le D_i\le 7$
All roots are integers whose absolute value is less than or equal to $150$.
The polynomial evaluated at $x$ where $-150\le x\le 150$ will always yield an absolute value less than $2^{63}-1$.

Subtask 1 [5%]

$N\le 20$

Subtask 2 [10%]

$N\le 300$

Subtask 3 [25%]

$N\le 2000$

Subtask 4 [60%]

No additional constraints.

Input Specification

On the first line, there is one integer, $N$, the number of polynomials to follow.
The next $N$ lines contain an integer $D$ representing the degree of the polynomial, followed by $D+1$ space-separated integers, the coefficients of the polynomial starting from the highest degree to the lowest degree.

Output Specification

Output a total of $N$ lines.
Line $i$ should contain the roots of the $i$-th polynomial in the input in increasing order. It is guaranteed that the polynomial has $D_i$ integer roots. You are to print the multiple roots.

Sample Input

3
2 2 -6 4
2 1 6 9
2 1 0 -9

Sample Output

1 2
-3 -3
-3 3