Problem Description
Factoring a polynomial is always a hard and important issue in mathematics teaching in middle schools. Teacher Liu loves teaching this issue very much, but his students are not good at it.
Yuanfang is the best student in Teacher Liu's class. Every time when Teacher Liu comes up with a hard problem and it seems no student can solve it, Liu always says: "Yuanfang , what do you think?"。
This week, Teacher Liu began to teach how to factor a polynomial. On Monday, Teacher Liu said : "Let's factor x2-1 ... Yuanfang, what do you think?"
On Tuesday, Teacher Liu said : "Let's factor x3-1 ... Yuanfang, what do you think?"
On Wednesday, Teacher Liu said : "Let's factor x4-1 ... Yuanfang, what do you think?"
…..
On Friday, Yuanfang got crazy. She wanted to solve this problem permanently. So she came to you, the only programmer she knows, for help.
You should write a program to factor the polynomial xn-1. In other words, represent the polynomial xn-1 by a product of irreducible polynomials in which coefficients are all integers.
Input
There are several test cases. Every case is an integer n in a line (n≤1100) meaning that you should factor the polynomial xn-1.
Input ends with n=0.
Output
We print polynomials like this:
1.x2 to x^2;
2.x3-1 to x^3-1;
3.x6-2x4+1 to x^6-2x^4+1.
For each test case, you should print the result polynomials in a certain order. To sort the polynomials, we compare the coefficients of them from high-degree to low-degree. The coefficient with a smaller absolute value has a smaller order. When absolute values are the same, negative coefficient has a smaller order. Please print the result polynomials from small order to large order.
In the result, put every factor polynomial between a pair of parentheses(Except that the result is just x-1 as shown in sample). Every factor polynomial must satisfy the following conditions:
1.It can't be factored any more.
2.All the terms of the same degree must be combined.
3.No term's coefficient is 0.
4.The terms appear in the descending order by degree.
5.All coefficients are integers.
Sample Input
1
2
3
4
5
6
0
Sample Output
x-1
(x-1)(x+1)
(x-1)(x^2+x+1)
(x-1)(x+1)(x^2+1)
(x-1)(x^4+x^3+x^2+x+1)
(x-1)(x+1)(x^2-x+1)(x^2+x+1)
