Factorize xⁿ-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.