#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e6+5;using vec=vector<int>;
int T,n,pr[N/10],phi[N],mu[N],mx[N];
inline void init(int n=N-5)
{
	phi[1]=mu[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!mx[i]) pr[++pr[0]]=i,phi[i]=i-1,mu[i]=-1,mx[i]=i;
		for(int j=1,p=2;i*p<=n&&j<=pr[0];p=pr[++j])
		{
			mx[i*p]=mx[i];
			if(!(i%p)){phi[i*p]=phi[i]*p;break;}
			phi[i*p]=phi[i]*(p-1);mu[i*p]=-mu[i];
		}
	}
}
inline bool operator<(const vec &A,const vec &B)
{
	if(A.size()^B.size()) return A.size()<B.size();
	for(int i=A.size()-1;~i;i--)
	{
		if(A[i]<B[i]) return 1;
		if(A[i]>B[i]) return 0;
	}return 0;
}
inline void print(const vec &A)
{
	cout<<'(';int sz=A.size()-1;
	for(int i=sz;~i;i--) if(A[i]!=0)
	{
		if(i!=sz&&A[i]>0) cout<<'+';
		if(!i){cout<<A[i];continue;}
		if(A[i]==-1) cout<<'-';
		else if(A[i]!=1) cout<<A[i];
		cout<<'x';if(i>1) cout<<'^'<<i;
	}cout<<')';
}
vec ph[N];int p[9],d[1<<9];
#define pt __builtin_parity
inline void get(int n)
{
	auto &g=ph[n];if(g.size()) return;const int m=phi[n];
	g.resize(m+1);g[0]=1;int t=0,x=n;
	for(int u;x>1;){u=p[t++]=mx[x];while(!(x%u)) x/=u;}
	for(int i=d[0]=1,B;i<(1<<t);i++) B=__lg(i),d[i]=d[i^(1<<B)]*p[B];
	for(int i=0;i<(1<<t);i++)
	{
		int x=n/d[i];
		if(pt(i)) for(int j=x;j<=m;j++) g[j]+=g[j-x];
		else for(int j=m;j>=x;j--) g[j]-=g[j-x];
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;init();
	ph[1]={-1,1};ph[2]={1,1};
	while(T--)
	{
		cin>>n;vector<int>d{1};
		for(int i=2;i<=n/2;i++) if(!(n%i)) d.push_back(i);d.push_back(n);
		for(int i:d) get(i);
		sort(d.begin(),d.end(),[](int x,int y){return ph[x]<ph[y];});
		for(int i:d) print(ph[i]);cout<<"\n";
	}
	return 0;
}