네가 원하는 대로 불러

수학에 빠진 전형적인 사람인 Taylor는 과학 계산 도구를 잘 다루지만 프로그래밍 기반 지식에는 약해서 늘 무력감을 느낀다.

최근 그는 (x^n - 1) 꼴의 다항식을 정수 위에서 인수분해하는 작업을 했다. 이는 그 꼴의 다항식을 계수가 모두 정수인 기약 인수의 곱으로 나타내는 것이다.

원분 다항식을 알게 된 그는 (x^n - 1 = \prod_{d|n}{\Phi_d(x)})이고, 여기서 각 인수가 정수 위에서 기약 다항식이라는 사실을 알았다. 또한 (\Phi_n(x) = \prod_{1 \le k \le n, \text{gcd}(n, k) = 1}{\left(x - w_n^k\right)})이며, 여기서 (w_n = \cos{\left(\frac{2\pi}{n}\right)} + \sqrt{-1}\sin{\left(\frac{2\pi}{n}\right)})는 차수 (n)의 단위 복소근이고 (\text{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_1(x))를 빼면 (\Phi_n(x))의 계수가 앞뒤로 대칭이라는 점, (p)가 소수일 때 (\Phi_{p^e}(x) = \Phi_p\left(x^{p^{e-1}}\right))라는 점 같은 관찰을 할 수도 있지만, 문제를 푸는 데는 쓸모가 없을지도 모른다.

첫째 줄에는 테스트 케이스의 수 (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))의 계수보다 작다는 것과 같다.

한 다항식의 출력 형식: 다항식의 모든 항을 높은 차수에서 낮은 차수 순서로 출력하며, 각 항은 (\pm c_kx^k) 꼴로 만든다. 또한 다음을 따른다.

1. 계수가 0인 항은 생략한다.
2. 첫 항의 부호((\pm))는 그 항의 계수가 양수이면 생략한다.
3. (c_k = 1)이면 (k = 0)이 아닌 한 (c_k)를 생략한다.
4. (x^0)은 생략하고 (x^1)은 간단히 (x)로 쓴다.

표준 출력 파일의 크기는 26 MiB를 넘지 않는다.