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
#include <bits/stdc++.h>
using namespace std;

int t,k,x,l,y,razem,c,ile,liczba;
int pierwsze[30] = {2,3,5,7,11,13,17};
int ilepierwszych = 5;
vector<pair<int,int> > wyniki;
long long rozmiar;
pair<int,int>  yd;
vector <int> wektor[101];

void xd(long long x, int suma,int start)
{
    for(int i=start;i<ilepierwszych;i++)
    {
        if(x*pierwsze[i]<=k && suma+pierwsze[i]<=100)
        {
            wyniki.push_back(make_pair(x*pierwsze[i],suma+pierwsze[i]));
            rozmiar++;
            xd(x*pierwsze[i],suma+pierwsze[i],i);
        }
        if(x*pierwsze[i]>k || suma+pierwsze[i]>100) break;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> t;
    k=1e9;
    wyniki.push_back(make_pair(1,1));
    xd(1,0,0);
    wyniki.push_back(make_pair(k+1,0));
    sort(wyniki.begin(),wyniki.end());
    for(int i=0;i<t;i++)
    {
        cin >> l;
        razem=0;
        x=0;
        c=0;
        ile=0;
        while(l-x>0 && ile<=20000)
        {
            vector<pair<int,int> >::iterator low;
            low = lower_bound(wyniki.begin(),wyniki.end(),make_pair(l-x,0));
            yd = *(low-c);
            y = yd.first;
            if(y>l-x)
            {
                yd = *(low-c-1);
                y = yd.first;
            }
            x+= y;
            razem+=yd.second;
            if(razem>100)
            {
                x=0;
                c++;
                razem=0;
                wektor[i].clear();
            }
            else
            {
                wektor[i].push_back(y);
            }
            ile++;
        }
        if(ile>20000) cout << "NIE" << endl;
        else
        {
            for(int j=0;j<wektor[i].size();j++)
            {
                liczba = wektor[i][j];
                if(liczba==1)
                {
                    if(wektor[i].size()==1)
                    {
                        cout << "1";
                    }
                    else
                    {
                        cout << "1";
                    }
                    if(j<wektor[i].size()-1) cout << "+";
                }
                else
                {
                    while(liczba>1)
                    {
                        for(int m=0;m<ilepierwszych;m++)
                        {
                            if(liczba%pierwsze[m]==0)
                            {
                                cout << "(";
                                for(int n=0;n<pierwsze[m]-1;n++)
                                {
                                    cout << "1+";
                                }
                                cout << "1)";
                                if(liczba/pierwsze[m]!=1) cout << "*";
                                liczba/=pierwsze[m];
                                //cout << pierwsze[m] << " ";
                                break;
                            }
                        }
                    }
                    if(j<wektor[i].size()-1) cout << "+";
                }
            }
            cout << endl;
        }
    }
}