FACTOR1 - Factorization, Factorization, Factorization

Factorize xn-1 into several irreducible polynomials over the integers.

Input

Multiple test cases. For each test case:

A single line - n. (2 ≤ n ≤ 1200).

Input terminates by a single zero.

Output

For each test case, output the factorization of the given polynomial.

There are multiple ways to express the factorization of a polynomial. To make it unique, we sort the irreducible polynomials according to the following rules:

Lower order polynomials are always lexicographically smaller than higher order polynomials. Same order polynomials should be sorted by their coefficients. We compare the coefficients from high degree terms to low degree terms, including the omitted terms, which the coefficients are regard as 0. Coefficients are being compared first by absolute value then by sign. Smaller absolute values are lexicographically smaller. For the same absolute value, negative coefficients are lexicographically smaller than positive coefficients.

See example for more output format details.

Example

Input:
12
0

Output:
(x-1)(x+1)(x^2+1)(x^2-x+1)(x^2+x+1)(x^4-x^2+1)

Hint

There should not be a "*" between digit and x, i.e. -2x^2 should be printed as -2x^2.


Added by:Fudan University Problem Setters
Date:2009-05-23
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Fudan University Local Contest #1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.