#include<bits/stdc++.h>
using namespace std;
namespace gza{
	#define pb push_back
	#define MT int TTT=R;while(TTT--)
	#define pc putchar
	#define R read()
	#define fo(i,a,b) for(int i=a;i<=b;i++)
	#define rep(i,a,b) for(int i=a;i>=b;i--)
	#define m1(a,b) memset(a,b,sizeof a)
	namespace IO
	{
		inline int read()
		{
		    int x=0;
		    char ch=getchar();
		    bool f=0;
		    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
		    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		    if(f) x=-x;
		    return x;    
		}
		template<typename T> inline void write(T x)
		{
		    if(x<0) pc('-'),x=-x;
		    if(x>9) write(x/10);
		    pc(x%10+'0');
		}
	};
	namespace math
	{
		inline int gcd(int a,int b)
		{
			int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;
		    b>>=bz;
		    while(a) a>>=az,t=a-b,b=a,az=__builtin_ctz(t<0?-t:t),a=t<0?-t:t;
		    return b<<z;
		}
		inline int qmi(int a,int b,int p)
		{
			int res=1;
			while(b)
			{
				if(b&1) res=res*a%p;
				a=a*a%p;
				b>>=1;
			}
			return res;
		}
		const int MAXN=1e6+10;
		int my_fac[MAXN],my_inv[MAXN];
		void init_binom(int mod)
		{
			my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
			my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
		}
		int binom(int a,int b,int mod)
		{
			return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
		}
	};
	using namespace IO;
	using namespace math;
	
	const int N=2e6+10;
	int n,maxx;
	int ask[N];
	int primes[N],cnt;
	bool vis[N];
	int phi[N],mu[N],minp[N];
	#define poly basic_string<int>
	poly ans[N];
	int abs(int x){return x>0?x:-x;}
	vector<int> t0,t1;
	//0:01背包1:完全背包
	void calc(int n)
	{
		t0.clear(),t1.clear();
		for(int i=1;i*i<=n;i++) if(n%i==0)
		{
			if(mu[i]==1) t0.pb(n/i);
			if(mu[i]==-1) t1.pb(n/i);
			if(i*i!=n)
			{
				if(mu[n/i]==1) t0.pb(i);
				if(mu[n/i]==-1) t1.pb(i);
			}
		}
		ans[n].resize(phi[n]+1);
		ans[n][0]=1;
		// cout<<n<<endl;
		// for(auto j:tt[n][0]) cout<<j<<' ';
		// cout<<endl;
		// for(auto j:tt[n][1]) cout<<j<<' ';
		// cout<<endl;
		for(auto j:t0) rep(i,phi[n],j) ans[n][i]-=ans[n][i-j];
		for(auto j:t1) fo(i,j,phi[n]) ans[n][i]+=ans[n][i-j];
		// for(auto j:ans[n]) cout<<j<<' ';
		// cout<<endl;
		vis[n]=1;
	}
	bool operator< (const poly& A,const poly& B)
	{
		if(A.size()!=B.size()) return A.size()<B.size();
		rep(i,(int)A.size()-1,0)
		{
			if(A[i]!=B[i]) return A[i]<B[i];
			else if((A[i]<0)!=(B[i]<0)) return A[i]<0;
		}
		return 0;
	}
	void output(const poly& a)
	{
		pc('(');
		rep(i,(int)a.size()-1,0) if(a[i]!=0)
		{
			if(i!=(int)a.size()-1&&a[i]>0) pc('+');
			if(a[i]<0) pc('-');
			if(abs(a[i])!=1) write(abs(a[i]));
			if(i!=0)
			{
				pc('x');
				if(i!=1) pc('^'),write(i);
			}
			else write(abs(a[i]));
		}
		pc(')');
	}
	void get_primes(int n)
	{
		phi[1]=mu[1]=1;
		fo(i,2,n)
		{
			if(!vis[i]) primes[++cnt]=i,phi[i]=i-1,mu[i]=-1,minp[i]=i;
			for(int j=1;j<=cnt&&i*primes[j]<=n;j++)
			{
				vis[i*primes[j]]=1;
				minp[i*primes[j]]=primes[j];
				if(primes[j]==minp[i])
				{
					phi[i*primes[j]]=phi[i]*primes[j];
					break;
				}
				phi[i*primes[j]]=phi[i]*(primes[j]-1);
				mu[i*primes[j]]=-mu[i];
			}
		}
	}
	vector<int> d;
	void solve(int _)
	{
		n=ask[_];
		if(n==1) return void(puts("x-1"));
		d.clear();
		for(int i=1;i*i<=n;i++) if(n%i==0)
		{
			d.pb(i);
			if(i*i!=n) d.pb(n/i);
		}
		for(auto j:d) if(!vis[j]) calc(j);
		sort(d.begin(),d.end(),[&](int a,int b){return ans[a]<ans[b];});
		for(auto j:d) output(ans[j]);
		vis[n]=1;
		puts("");
	}
	void main(){
		int T=R;
		fo(i,1,T) ask[i]=R,maxx=max(maxx,ask[i]);
		get_primes(maxx);
		m1(vis,0);
		calc(1);
		for(auto& j:ans[1]) j=-j;
		fo(i,1,T) solve(i);
	}
}
signed main(){
	// freopen("factorization.in","r",stdin);
	// freopen("factorization.out","w",stdout);
	gza::main();
}