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 <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
using namespace std;

vector< int > liczby = { 
	2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 67, 71, 73, 
	79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151 
};
int ostatnio_sprawdzona = liczby.back();

bool pierwsza(int l)
{
	for( int i = 0; i < liczby.size(); ++i ) {
		if( liczby[i] >= l ) {
			return true;
		}
		if( l % liczby[i] == 0 ) {
			return false;
		}
	}
	return true;
}

void przygotuj_liczby(int ile = 10)
{
	int znalezione = 0;
	while( znalezione < ile ) {
		ostatnio_sprawdzona++;
		if( pierwsza(ostatnio_sprawdzona) ) {
			liczby.push_back(ostatnio_sprawdzona);	
			znalezione += 1;	
		}
	}
}

int dzielnik(int cel)
{
	int maks = sqrt(cel);
	int i = 0;
	while( (i < liczby.size()) || (liczby.back() <= maks) ) {
		while( i < liczby.size()  ) {
			if ( liczby[i] > maks ) {
				return cel;
			}
			if( cel % liczby[i] == 0 ) {
				return liczby[i];
			}
			i++;	
		}
		przygotuj_liczby( 10 );
	}
	return cel;
}

struct Drzewo {
	char op;
	int cost;
	unique_ptr< Drzewo > lewy;
	unique_ptr< Drzewo > prawy;
	Drzewo( char c )
	{
		op = 0;
		cost = 1;
		lewy = nullptr;
		prawy = nullptr;
	}

	Drzewo( char op, unique_ptr< Drzewo > lewy, unique_ptr< Drzewo > prawy )
		: op(op), lewy(std::move(lewy)), prawy(std::move(prawy))
	{
		cost = this->lewy->cost + this->prawy->cost;
	}
};

unique_ptr< Drzewo > rozwiaz(int cel)
{
	if( cel == 1 ) {
		return unique_ptr< Drzewo >( new Drzewo(0) );
	}

	int d = dzielnik(cel);
	assert(d > 1);

	if( d == cel ) {
		return unique_ptr< Drzewo >( new Drzewo ('+', rozwiaz( cel - 1 ), rozwiaz( 1 ) ) );
	}
	else {
		return unique_ptr< Drzewo >( new Drzewo ('*', rozwiaz( d ), rozwiaz( cel / d ) ) );
	}
}

string rozpisz( Drzewo const * const d )
{
	if ( d->cost > 100 ) {
		return "NIE";
	}
	else if( d->op == '+' ) {
		return "(" + rozpisz( d->lewy.get() ) + "+" + rozpisz( d->prawy.get() ) + ")";
	}
	else if ( d->op == '*' ) {
		return rozpisz( d->lewy.get() ) + "*" + rozpisz( d->prawy.get() );
	}
	else {
		return "1";
	}
}

void wypisz_wynik(int cel)
{
	auto d = rozwiaz( cel );
	string s = rozpisz( d.get() );
	cout << s << "\n";
}

int main()
{
	ios_base::sync_with_stdio( false );
	int t; cin >> t;
	for( int i = 0; i < t; ++i ) {
		int cel; cin >> cel;
		wypisz_wynik(cel);
	}
}