// superyijin AK IOI
// wangsiyuanZP AK IOI
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define ld long double
#define Complex complex<ld>
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pair<int, int>>
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
#define pcnt __builtin_popcountll
using namespace std;
const int inf = (sizeof(int) == 4 ? 0x3f3f3f3f : 0x3f3f3f3f3f3f3f3f);
const int mod = 998244353;
const ld eps = 1e-7, pi = acos(-1);
void chkmin(int &x, int y) { x = min(x, y); }
void chkmax(int &x, int y) { x = max(x, y); }
void inc(int &x, int y) { x = (x + y >= mod ? x + y - mod : x + y); }
void dec(int &x, int y) { x = (x - y < 0 ? x - y + mod : x - y); }
int ksm(int a, int b)
{
	int t = 1;
	while (b)
	{
		if (b & 1) t = t * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return t;
}
int ksm(int a, int b, int p)
{
	int t = 1;
	while (b)
	{
		if (b & 1) t = t * a % p;
		a = a * a % p, b >>= 1;
	}
	return t;
}
bool Mbe;
const int N = 1e6 + 10;
struct Bit
{
	int t[N];
	Bit() { memset(t, 0, sizeof(t)); }
	void clear(int n) { for (int i = 1; i <= n; i++) t[i] = 0; }
	int lowbit(int x) { return x & -x; }
	void add(int x, int y) { while (x < N) t[x] += y, x += lowbit(x); }
	int sum(int x)
	{
		int ans = 0;
		while (x >= 1) ans += t[x], x -= lowbit(x);
		return ans;
	}
	int query(int l, int r) { return sum(r) - sum(l - 1); }
};
int fac[N], invfac[N];
void init(int n)
{
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
	invfac[n] = ksm(fac[n], mod - 2);
	for (int i = n - 1; i >= 0; i--) invfac[i] = invfac[i + 1] * (i + 1) % mod;
}
int A(int n, int m)
{
	if (m < 0 || m > n) return 0;
	return fac[n] * invfac[n - m] % mod;
}
int C(int n, int m)
{
	if (m < 0 || m > n) return 0;
	return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
int prime[2000010], phi[2000010], mu[2000010];
bool isprime[2000010];
vi vec[2000010];
vi solve(int n)
{
	if (n == 1) return {-1, 1};
	if (!vec[n].empty()) return vec[n];
	vi v[2], ans{1};
	ans.resize(phi[n] + 1);
	for (int i = 1; i * i <= n; i++)
	{
		if (n % i != 0) continue;
		if (mu[n / i] == 1) v[0].pb(i);
		if (mu[n / i] == -1) v[1].pb(i);
		if (i * i < n)
		{
			if (mu[i] == 1) v[0].pb(n / i);
			if (mu[i] == -1) v[1].pb(n / i);
		}
	}
	for (auto i : v[0]) for (int j = phi[n]; j >= 0; j--) (j + i <= phi[n] ? ans[j + i] += ans[j] : 0), ans[j] = -ans[j];
	for (auto i : v[1]) for (int j = 0; j <= phi[n]; j++) ans[j] = -ans[j], (j + i <= phi[n] ? ans[j + i] -= ans[j] : 0);
	return vec[n] = ans;
}
bool cmp(vi x, vi y)
{
	if (x.size() != y.size()) return x.size() < y.size();
	for (int i = x.size() - 1; i >= 0; i--) if (x[i] != y[i]) return x[i] < y[i];
	return 1;
}
string f1(int x)
{
	x = abs(x);
	if (x == 1) return "";
	return to_string(x);
}
string f2(int x)
{
	if (x == 0) return "";
	if (x == 1) return "x";
	return "x^" + to_string(x);
}
string calc(int x, int y)
{
	if (abs(x) == 1 && y == 0) return "1";
	return f1(x) + f2(y);
}
void Main()
{
	int n;
	cin >> n;
	vector<vi> ans;
	for (int d = 1; d <= n; d++)
	{
		if (n % d != 0) continue;
		ans.pb(solve(d));
	}
	sort(ans.begin(), ans.end(), cmp);
	for (auto v : ans)
	{
		cout << "(";
		cout << calc(v.back(), v.size() - 1);
		for (int i = v.size() - 2; i >= 0; i--)
		{
			if (v[i] == 0) continue;
			if (v[i] > 0) cout << "+";
			else cout << "-";
			cout << calc(v[i], i);
		}
		cout << ")";
	}
	cout << '\n';
}
bool Med;
signed main()
{
	// freopen("factorization.in", "r", stdin);
	// freopen("factorization.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << "MB" << endl;
	memset(isprime, true, sizeof(isprime));
	isprime[1] = false, mu[1] = 1;
	int m = 0;
	for (int i = 2; i <= 2e6; i++)
	{
		if (isprime[i]) prime[++m] = i, phi[i] = i - 1, mu[i] = -1;
		for (int j = 1; j <= m && i * prime[j] <= 2e6; j++)
		{
			isprime[i * prime[j]] = false;
			if (i % prime[j] == 0)
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				mu[i * prime[j]] = 0;
				break;
			}
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			mu[i * prime[j]] = -mu[i];
		}
	}
	int T;
	cin >> T;
	while (T--) Main();
	return 0;
}
// superyijin AK IOI
// wangsiyuanZP AK IOI