{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eAs a stereotyped math fanatic, Taylor is expert on utilizing scientific computing tools but he is poor at programming infrastructures, which brings him endless powerlessness.\u003cbr\u003eRecently he worked on factoring polynomials of the form $(x^n - 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.\u003cbr\u003eWith knowledge of the cyclotomic polynomial, he has known that $x^n - 1 \u003d \\prod_{d | n}{\\Phi_d(x)}$ where each factor of that is just an irreducible polynomial over the integers. Moreover, $\\Phi_n(x) \u003d \\prod_{1 \\leq k \\leq n, \\gcd(n, k) \u003d 1}{\\left(x - {w_n}^k\\right)}$, where $w_n \u003d \\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 $\\gcd(n, k)$ is the greatest common divisor of $n$ and $k$.\u003cbr\u003eAlthough he found such a conclusion, he couldn\u0027t obtain the result of some high-degree polynomial in a few seconds. Could you please help him accomplish some factorizations of $(x^n - 1)$?\u003cbr\u003eHere are some examples:\u003cbr\u003e $\\Phi_1(x) \u003d x - 1$;\u003cbr\u003e $\\Phi_2(x) \u003d x + 1$, $x^2 - 1 \u003d (x - 1) (x + 1)$;\u003cbr\u003e $\\Phi_3(x) \u003d x^2 + x + 1$, $x^3 - 1 \u003d (x - 1) (x^2 + x + 1)$;\u003cbr\u003e $\\Phi_4(x) \u003d x^2 + 1$, $x^4 - 1 \u003d (x - 1) (x + 1) (x^2 + 1)$;\u003cbr\u003e $\\Phi_6(x) \u003d x^2 - x + 1$, $x^6 - 1 \u003d (x - 1) (x + 1) (x^2 - x + 1) (x^2 + x + 1)$;\u003cbr\u003e $\\Phi_{12}(x) \u003d x^4 - x^2 + 1$, $x^{12} - 1 \u003d (x - 1) (x + 1) (x^2 - x + 1) (x^2 + 1) (x^2 + x + 1) (x^4 - x^2 + 1)$.\u003cbr\u003e\u003cbr\u003eOops! You might have some observations such as the degree of $\\Phi_n(x)$ equals to $\\varphi(n)$, coefficients of $\\Phi_n(x)$ are the same back-to-front as front-to-back except for $\\Phi_1(x)$, $\\Phi_{p^e}(x) \u003d \\Phi_{p}\\left(x^{p^{e - 1}}\\right)$ when $p$ is prime, etc. , but they might be worthless for solving.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains one integer $T$, indicating the number of test cases.\u003cbr\u003eEach of the following $T$ lines describes a test case and contains only one integer $n$.\u003cbr\u003e$1 \\leq T \\leq 100$, $2 \\leq n \\leq 10^5$.\u003cbr\u003eIt is guaranteed that the sum of $n$ in all test cases does not exceed $5 \\cdot 10^6$."}},{"title":"Output","value":{"format":"HTML","content":"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.\u003cbr\u003e\u003cb\u003eOrder of polynomials:\u003c/b\u003e 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 \u003d m + 1, m + 2, \\cdots)$ 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)$.\u003cbr\u003e\u003cb\u003eOutput format of one polynomial:\u003c/b\u003e Output all the terms of the polynomial from high-degree to low-degree, each of which should be formed as $\\pm c_{k} x^{k}$. Additionally,\u003cbr\u003e1. One term should be omitted if its coefficient is zero.\u003cbr\u003e2. The sign of the first term ($\\pm$) should be omitted if the coefficient of that is positive.\u003cbr\u003e3. When $c_k \u003d 1$, $c_k$ should be omitted unless $k \u003d 0$.\u003cbr\u003e4. $x^0$ should be omitted while $x^1$ should be written as a simple $x$.\u003cbr\u003eIt is guaranteed that the size of the standard output file does not exceed $26$ MiB.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n2\r\n3\r\n4\r\n6\r\n12\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e(x-1)(x+1)\r\n(x-1)(x^2+x+1)\r\n(x-1)(x+1)(x^2+1)\r\n(x-1)(x+1)(x^2-x+1)(x^2+x+1)\r\n(x-1)(x+1)(x^2-x+1)(x^2+1)(x^2+x+1)(x^4-x^2+1)\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}