[HDOJ3205]Factorization

LMY 和 YY 都是数学爱好者，他们经常一起寻找并解决有趣的数学问题。

一天，他们发现，虽然多项式 $x^n-1$ 看起来十分简单，却可以分解为许多次数较高的多项式。他们想知道如何将其分解为若干个整数系数不可约多项式。

这里称一个多项式是“不可约”的，当且仅当它的所有系数互质，并且不能在整数系数多项式范围内继续分解。

请你帮助 LMY 和 YY，将 $x^N-1$ 分解为若干个整数系数不可约多项式的乘积。

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含一个整数 $N$。

当输入一行 $0$ 时，表示输入结束，该行不需要处理。

输出格式

对于每组测试数据，输出 $x^N-1$ 的因式分解结果。

多项式应按照通常的书写习惯输出，例如 $x^5$、$5x^2$、$3x$、$x^2-x$。

同一个多项式的因式分解可能有多种排列方式。为了使输出唯一，所有不可约因式按照以下规则排序：

• 次数较低的多项式排在次数较高的多项式之前；
• 次数相同的多项式按照系数进行比较；
• 比较系数时，从最高次项到常数项依次比较，未出现的项视为系数为 $0$；
• 比较两个系数时，先比较其绝对值，绝对值较小的排在前面；
• 若两个系数的绝对值相同，则负数排在正数前面。

样例输入

2
3
4
5
6
12
256
0

样例输出

(x-1)(x+1)
(x-1)(x^2+x+1)
(x-1)(x+1)(x^2+1)
(x-1)(x^4+x^3+x^2+x+1)
(x-1)(x+1)(x^2-x+1)(x^2+x+1)
(x-1)(x+1)(x^2+1)(x^2-x+1)(x^2+x+1)(x^4-x^2+1)
(x-1)(x+1)(x^2+1)(x^4+1)(x^8+1)(x^16+1)(x^32+1)(x^64+1)(x^128+1)

数据范围

• 对于每组测试数据，$2\le N\le 1001$；
• 输入以 $N=0$ 结束。

来源与许可

本题原为 HDOJ 3205「Factorization」，题面与测试数据整理自 BZOJ 1848。

样例 1

输入

2
3
4
5
6
12
256
0

输出

(x-1)(x+1)
(x-1)(x^2+x+1)
(x-1)(x+1)(x^2+1)
(x-1)(x^4+x^3+x^2+x+1)
(x-1)(x+1)(x^2-x+1)(x^2+x+1)
(x-1)(x+1)(x^2+1)(x^2-x+1)(x^2+x+1)(x^4-x^2+1)
(x-1)(x+1)(x^2+1)(x^4+1)(x^8+1)(x^16+1)(x^32+1)(x^64+1)(x^128+1)