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
#include <bits/stdc++.h>
using namespace std;
int x,t;
bool zlozone[100007];
string wynik;
vector <int> pierwsze,X; //do 10^5
void sito(){
	for (int i=2; i*i<100001; i++)
		if (!zlozone[i])
			for (int j=i*2; j<100001; j+=i)
				zlozone[j]=true;
	for (int i=2; i<100001; i++)
		if (!zlozone[i])
			pierwsze.push_back(i);
}
bool JestPierwsza(int number){
	for (int i=0; i<pierwsze.size(); i++){
		if (pierwsze[i]<number && number%pierwsze[i]==0)
			return false;
		else if (pierwsze[i]>=number || i==pierwsze.size()-1)
			return true;
	}
}
vector <int> rozloz(int number){
	X.clear();
	int it=0;
	while (number>1 && it<pierwsze.size()){
		while (number%pierwsze[it]==0){
			number/=pierwsze[it];
			X.push_back(pierwsze[it]);
		}
		it++;
	}
	if (number>1)
		X.push_back(number);
	return X;
}
string wypisz(int number){
	string nazwa="(";
	while (JestPierwsza(number)==true && number!=0){
		number--;
		nazwa+="1+";
	}  
	if (number==0)
		nazwa[nazwa.length()-1]=')'; 
	else{
		vector <int> rozklad=rozloz(number);
		for (int i=0; i<rozklad.size()-1; i++)
			nazwa+=wypisz(rozklad[i])+'*';
		nazwa+=wypisz(rozklad.back())+')';
	}
	return nazwa;
}
bool ok(){
	int suma=0;
	for (int i=0; i<wynik.length(); i++)
		if (wynik[i]=='1')
			suma++;
	if (suma>100)
		return false;
	return true;
}
int main(){
	ios_base::sync_with_stdio(0);
	sito();
	cin>>t;
	for (int o=0; o<t; o++){
		cin>>x;
		wynik=wypisz(x);
		if (ok()==true){
			for (int i=1; i<wynik.length()-1; i++)
				cout<<wynik[i];
			cout<<endl;
		}
		else
			cout<<"NIE"<<endl;
	}
	return 0;
}