405804: GYM102114 C Call It What You Want

As a stereotyped math fanatic, Taylor is expert on utilizing scientific computing tools but he is poor at programming infrastructures, which brings him endless powerlessness.

Recently he worked on factoring polynomials of the form (xⁿ - 1) over the integers, which aims to express any polynomial of that form as some product of irreducible factors whose coefficients are all in the integers.

With knowledge of the cyclotomic polynomial, he has known that where each factor of that is just an irreducible polynomial over the integers. Moreover, , where is the unit complex root of degree n and is the greatest common divisor of n and k.

Although he found such a conclusion, he couldn't obtain the result of some high-degree polynomial in a few seconds. Could you please help him accomplish some factorizations of (xⁿ - 1)?

Here are some examples:

• Φ₁(x) = x - 1;
• Φ₂(x) = x + 1, x² - 1 = (x - 1)(x + 1);
• Φ₃(x) = x² + x + 1, x³ - 1 = (x - 1)(x² + x + 1);
• Φ₄(x) = x² + 1, x⁴ - 1 = (x - 1)(x + 1)(x² + 1);
• Φ₆(x) = x² - x + 1, x⁶ - 1 = (x - 1)(x + 1)(x² - x + 1)(x² + x + 1);
• Φ₁₂(x) = x⁴ - x² + 1, x¹² - 1 = (x - 1)(x + 1)(x² - x + 1)(x² + 1)(x² + x + 1)(x⁴ - x² + 1).

Oops! You might have some observations such as the degree of Φ_n(x) equals to φ(n), coefficients of Φ_n(x) are the same back-to-front as front-to-back except for Φ₁(x), when p is prime, etc. , but they might be worthless for solving.

The first line contains one integer T, indicating the number of test cases.

Each of the following T lines describes a test case and contains only one integer n.

1 ≤ T ≤ 100, 2 ≤ n ≤ 10⁵.

It is guaranteed that the sum of n in all test cases does not exceed 5·10⁶.

For each test case, output the factorization as a string without any space in one line, where the polynomials should be sorted in a particular order and each polynomial should be printed in a particular format and enclosed in a pair of parentheses.

Order of polynomials: The order of polynomial f(x) is lower than that of polynomial g(x) if and only if there exists a non-negative integer m such that the coefficient of x^k (k = m + 1, m + 2, ...) in f(x) equals to that of g(x) but the coefficient of x^m in f(x) is less than that of g(x).

Output format of one polynomial: Output all the terms of the polynomial from high-degree to low-degree, each of which should be formed as  ± c_kx^k. Additionally,

1. One term should be omitted if its coefficient is zero.
2. The sign of the first term ( ± ) should be omitted if the coefficient of that item is positive.
3. When c_k = 1, c_k should be omitted unless k = 0.
4. x⁰ should be omitted while x¹ should be written as a simple x.

It is guaranteed that the size of the standard output file does not exceed 26 MiB.

5
2
3
4
6
12

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