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
#include <iostream>
#include <map>
#include <cmath>

using namespace std;

int t,n;
int _used, maxUsed=0;
typedef pair<string, int> PSI;
map<int,PSI> codes;
bool success;

string analyse(int n, int& left)
{
	auto iter = codes.find(n);
	if(iter!=codes.end())
	{
		left -= iter->second.second;
		return iter->second.first;
	}
	int end = sqrt(n);
	for(int i=2; i<=end; ++i)
	{
		if(n%i==0)
		{
			PSI wyn;
			wyn.second = left;
			wyn.first = string("(")+analyse(n/i, left)+")*("+analyse(i, left)+")";
			wyn.second -= left;
			codes[n] = wyn;
			return wyn.first;
		}
	}
	/// liczba pierwsza - wynik to analyse(n-1) "+1"
	PSI wyn;
	wyn.second = left;
	wyn.first = analyse(n-1, left)+"+"+analyse(1, left);
	wyn.second -= left;
	codes[n] = wyn;
	return wyn.first;
}

string process(int n, int left)
{
	if(n==1)
		return "1";
	string result;
	int end = sqrt(n);
	for(int i=2; i<=end && i<n; ++i)
	{
		while(n%i == 0)
		{
			if(result.empty())
				result = string("(")+analyse(i, left)+")";
			else
				result += string("*(")+analyse(i, left)+")";
			n /= i;
		}
	}
	if(n>1)
	{
		if(result.empty())
			result = string("(")+analyse(n, left)+")";
		else
			result += string("*(")+analyse(n, left)+")";
	}
	if(left<0)
		success = false;
	_used = 100-left;
	return result;
}

int maxTime=0;

int main()
{
	codes[1] = make_pair(string("1"), 1);
	ios_base::sync_with_stdio(0);
	string result;
////	for(int n=1000000000; n>1; --n)
//	for(int i=1;i<=1000000000; ++n)
//	{
//		int t1 = GetTickCount();
//		result = process(n, 100);
//		int dt = GetTickCount()-t1;
//		if(dt>maxTime)
//		{
//			maxTime = dt;
//			cout << "##" << n << " -> " << maxTime << " ms" << endl;
//		}
//		if(_used > maxUsed)
//		{
//			maxUsed = _used;
//			cout << n << "\t" << _used << endl;
//		}
//	}
	cin>>t;
	while(t--)
	{
		cin>>n;
		success=true;
		result = process(n, 100);
		if(success)
			cout<<result<<endl;
		else
			cout<<"NIE"<<endl;
	}
	return 0;
}