1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define pii pair<int, int>

#define MAX 32000
#define LMT 179 // sqrt(MAX)
#define LEN 3432

unsigned base[MAX / 64], primes[LEN];

#define sq(x) ((x)*(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

// http://zobayer.blogspot.com/2009/09/segmented-sieve.html
void sieve()
{
	unsigned i, j, k;
	for (i = 3; i<LMT; i += 2)
		if (!chkC(base, i))
			for (j = i*i, k = i << 1; j<MAX; j += k)
				setC(base, j);
	primes[0] = 2;
	for (i = 3, j = 1; i<MAX; i += 2)
		if (!chkC(base, i))
			primes[j++] = i;
}


void rozwiaz(int n);
void wypisz(int n);
int ilosc(int num);
vector<pii> factors(int n);

int main()
{
	sieve();

	int t;
	scanf("%ld", &t);
	for (int i = 0; i < t; i++)
	{
		int n;
		scanf("%ld", &n);
		rozwiaz(n);
	}

	return 0;
}

void rozwiaz(int n)
{
	int il = ilosc(n);
	if (il > 100) {
		printf("NIE\n");
	} else {
		wypisz(n);
		printf("\n");
	}
}

void wypisz(int n)
{
	if (n == 1) { printf("1"); return; }
	if (n == 2) { printf("(1+1)"); return; }
	if (n == 3) { printf("(1+1+1)"); return; }
	if (n == 4) { printf("(1+1+1+1)"); return; }
	if (n == 5) { printf("(1+1+1+1+1)"); return; }

	auto facs = factors(n);

	for (int i = 0; i < facs.size(); i++) {

		for (int j = 0; j < facs[i].second; j++) {
			printf("(1+"); wypisz(facs[i].first - 1); printf(")");
			if (j < facs[i].second - 1) {
				printf("*");
			}
		}
		if (i < facs.size() - 1) {
			printf("*");
		}

	}
}

int ilosc(int num)
{
	if (num <= 5) { return num; }

	int res = 0;
	auto facs = factors(num);
	for (int i = 0; i < facs.size(); i++) {
		res += ((1 + ilosc(facs[i].first - 1)) * facs[i].second);
	}

	return res;
}

vector<pii> factors(int num)
{
	vector<pii> factors;

	int expo = 0;
	for (int i = 0; primes[i] <= sqrt(num); i++)
	{
		expo = 0;
		int prime = primes[i];
		while (num % prime == 0) {
			expo++;
			num = num / prime;
		}
		if (expo>0)
			factors.push_back(make_pair(prime, expo));
	}

	if (num >= 2)
		factors.push_back(make_pair(num, 1));

	return factors;
}