Description

In the present problem, we always assume that all the polynomials mentioned have the following properties (take f(x) for example ):

(1) 0 < deg(f) <= 20, so we can assume that f(x) has the following form: f(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x+a0 (an!=0 and 1<=n<=20)

(2) ai ( i=0,1,...,n ) is integer, and ?2^31<=ai<=2^31-1; (3) an = 1.

We call a polynomial G(x) "good" polynomial, when there is no polynomial F(x) such that

F²|G

Given a polynomial f(x), it is known that f(x) can be factorized as follow: f(x)=Gt^mtG_t-1^m_t-1...G1^m1 (Gi is good and mt>m_t-1>...>m1>=1)

It抯 easy to prove that this way of factorizing is unique. You job is to factorize the given polynomials in this way.

To make input and output easy, a polynomial f(x)

f(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x+a0 (an!=0 and 1<=n<=20)

is represented as n an a_n-1 ... a1 a0

In this representation, we use (n+2) integers, which are separated by single blanks.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Every case gives a polynomial in a single line.

Output

For each test case, output the corresponding result in the following form (where the meaning of those characters is taken as just mentioned):

t m_t

G

_t

m_t-1

G

_t-1

... m₁

G

₁

2
5 1 -3 4 -4 3 -1
2 1 -1 -2

2
3 1 1 -1
1 2 1 0 1
1
1 2 1 -1 -2

Hint

补充：

如果f=a1^n1*...at^nt(n1>...>nt)

那么要求a1,a2...at两两互质

Source

POJ Monthly