作为一个刻板的数学狂热者，Taylor 擅长使用科学计算工具，但他在编程基础方面却很薄弱，这让他感到无比无力。

最近，他致力于在整数域上对形如 $(x^n - 1)$ 的多项式进行因式分解，旨在将任何该形式的多项式表示为系数均为整数的不可约因子的乘积。

根据分圆多项式的知识，他已知 $x^n - 1 = \prod_{d|n} \Phi_d(x)$，其中每个因子都是整数域上的不可约多项式。此外，$\Phi_n(x) = \prod_{1 \le k \le n, \gcd(n, k) = 1} (x - w_n^k)$，其中 $w_n = \cos(\frac{2\pi}{n}) + \sqrt{-1} \sin(\frac{2\pi}{n})$ 是 $n$ 次单位复根，$\gcd(n, k)$ 是 $n$ 和 $k$ 的最大公约数。

尽管他得出了这样的结论，但他无法在几秒钟内得到某些高次多项式的分解结果。你能帮他完成一些 $(x^n - 1)$ 的因式分解吗？

以下是一些例子：

• $\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)$。

哎呀！你可能观察到了一些性质，例如 $\Phi_n(x)$ 的次数等于 $\phi(n)$，$\Phi_n(x)$ 的系数从后往前看与从前往后看相同（除了 $\Phi_1(x)$），当 $p$ 为素数时 $\Phi_{p^e}(x) = \Phi_p(x^{p^{e-1}})$ 等，但这些对于求解可能并没有什么用。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来的 $T$ 行，每行描述一个测试用例，仅包含一个整数 $n$。 $1 \le T \le 100, 2 \le n \le 10^5$。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^6$。

输出格式

对于每个测试用例，在一行中输出因式分解结果，作为一个不含空格的字符串。多项式应按特定顺序排序，且每个多项式应以特定格式打印并用一对圆括号括起来。

多项式的顺序：多项式 $f(x)$ 的顺序低于 $g(x)$，当且仅当存在一个非负整数 $m$，使得 $f(x)$ 中 $x^k$ ($k = m + 1, m + 2, \dots$) 的系数与 $g(x)$ 中对应项的系数相等，但 $f(x)$ 中 $x^m$ 的系数小于 $g(x)$ 中 $x^m$ 的系数。

单个多项式的输出格式：按从高次到低次的顺序输出多项式的所有项，每一项的形式应为 $\pm c_k x^k$。此外：

1. 如果某项系数为零，则应省略该项。
2. 如果首项系数为正，则应省略其符号（$\pm$）。
3. 当 $c_k = 1$ 时，应省略 $c_k$，除非 $k = 0$。
4. $x^0$ 应省略，而 $x^1$ 应写成简单的 $x$。

保证标准输出文件的大小不超过 $26 \text{ MiB}$。

样例

样例输入 1

5
2
3
4
6
12

样例输出 1

(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)