Call It What You Want

As a stereotyped math fanatic, Taylor is an expert at using scientific computing tools but poor at programming infrastructure, which brings him endless powerlessness.

Recently he worked on factoring polynomials of the form (x^n - 1) over the integers, which means expressing any polynomial of that form as a product of irreducible factors whose coefficients are all integers.

Knowing the cyclotomic polynomial, he has learned that (x^n - 1 = \prod_{d|n}{\Phi_d(x)}), where each factor is an irreducible polynomial over the integers. Moreover, (\Phi_n(x) = \prod_{1 \le k \le n, \text{gcd}(n, k) = 1}{\left(x - w_n^k\right)}), where (w_n = \cos{\left(\frac{2\pi}{n}\right)} + \sqrt{-1}\sin{\left(\frac{2\pi}{n}\right)}) is the unit complex root of degree (n) and (\text{gcd}(n, k)) is the greatest common divisor of (n) and (k).

Although he reached this conclusion, he could not obtain the result for some high-degree polynomials within a few seconds. Could you help him carry out the factorization of (x^n - 1)?

Here are some examples:

• (\Phi_1(x) = x - 1);
• (\Phi_2(x) = x + 1, x^2 - 1 = (x-1)(x+1));
• (\Phi_3(x) = x^2 + x + 1, x^3 - 1 = (x-1)(x^2+x+1));
• (\Phi_4(x) = x^2 + 1, x^4 - 1 = (x-1)(x+1)(x^2+1));
• (\Phi_6(x) = x^2 - x + 1, x^6 - 1 = (x-1)(x+1)(x^2-x+1)(x^2+x+1));
• (\Phi_{12}(x) = x^4 - x^2 + 1, x^{12} - 1 = (x-1)(x+1)(x^2-x+1)(x^2+1)(x^2+x+1)(x^4-x^2+1)).

Oops! You might make observations such as the degree of (\Phi_n(x)) equals (\phi(n)), the coefficients of (\Phi_n(x)) read the same backward as forward except for (\Phi_1(x)), or (\Phi_{p^e}(x) = \Phi_p\left(x^{p^{e-1}}\right)) when (p) is prime, but they might be worthless for solving the problem.

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

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

(1 \le T \le 100, 2 \le n \le 10^5).

It is guaranteed that the sum of (n) over all test cases does not exceed (5 \cdot 10^6).

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, \dots)) in (f(x)) equals that in (g(x)) but the coefficient of (x^m) in (f(x)) is less than that in (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 (\pm c_kx^k). Additionally,

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

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