#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define N 100000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int gcd(int x,int y)
{
	if (!y) return x;
	return gcd(y,x%y);
}
int T,n,length,phi[N+1],miu[N+1],delta[N+1];
vector<int>tong[N+1];
vector<int>v[N+1];
bool nprime[N+1];
bool cmp(vector<int>a,vector<int>b)
{
	if (a.size()!=b.size()) return a.size()<b.size();
	else return a<b;
}
vector<int>solve(int x)
{
	vector<int>p;
	for (int i=0;i<=phi[x];++i) delta[i]=0;
	delta[0]=1;
	for (int i=0;i<v[x].size();++i)
	{
		if (miu[v[x][i]]==1)
		{
			for (int j=phi[x];j>=x/v[x][i];--j) delta[j]-=delta[j-x/v[x][i]];
		}
		else
		{
			for (int j=x/v[x][i];j<=phi[x];++j) delta[j]+=delta[j-x/v[x][i]];
		}
	}
	for (int i=phi[x];i>=0;--i) p.push_back(delta[i]);
	return p;
}
void output(vector<int>p)
{
	printf("(");
	if (p.size()-1==1) printf("x");
	else printf("x^%d",p.size()-1);
	for (int i=p.size()-2;i>=0;--i)
	{
		if (p[i]==1)
		{
			if (i>1) printf("+x^%d",i);
			else if (i==1) printf("+x");
			else printf("+1");
		}
		else if (p[i]==-1)
		{
			if (i>1) printf("-x^%d",i);
			else if (i==1) printf("-x");
			else printf("-1");
		}
		else if (p[i]>0)
		{
			if (i>1) printf("+%dx^%d",p[i],i);
			else if (i==1) printf("+%dx",p[i]);
			else printf("+%d",p[i]);
		}
		else if (p[i]<0)
		{
			if (i>1) printf("%dx^%d",p[i],i);
			else if (i==1) printf("%dx",p[i]);
			else printf("%d",p[i]);
		}
	}
	printf(")");
	return;
}
int main()
{
	for (int i=1;i<=N;++i) miu[i]=1,phi[i]=i;
	for (int i=2;i<=N;++i)
		if (!nprime[i])
		{
			miu[i]=-1,phi[i]=i-1;
			for (int j=(i<<1);j<=N;j+=i)
			{
				if ((j/i)%i==0) miu[j]=0;
				miu[j]=-miu[j],phi[j]=phi[j]/i*(i-1),nprime[j]=1;
			}
		}
	for (int i=1;i<=N;++i)
		if (miu[i]!=0)
		{
			for (int j=i;j<=N;j+=i) v[j].push_back(i);
		}
	T=read();
	while (T--)
	{
		n=read(),length=0;
		for (int i=1;i<=n;++i)
			if (n%i==0)
				tong[++length]=solve(i),reverse(tong[length].begin(),tong[length].end());
		sort(tong+1,tong+length+1,cmp);
		for (int i=1;i<=length;++i) reverse(tong[i].begin(),tong[i].end()),output(tong[i]);
		puts("");
	}
	return 0;
}