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
#include <stdio.h>
#include <string>
#include <algorithm>
#include <sstream> 



std::string decomposition(int v) {
    std::stringstream out;
    bool empty=true;
    //printf("decomposition(%i)\n", v);

    if (v<=0) return "";
    if (v==1) return "1";
    if (v==2) return "(1+1)";
    if (v==3) return "(1+1+1)";
    if (v==5) return "(1+1+1+1+1)";
    
    while (v!=1) {
        for (int i=2; i<=v; ++i) {           
            if (v%i==0) {
                v = v/i;
                if (!empty) out<<"*";
                empty=false;
                if (i==2) {
                    out<<decomposition(2);
                } else if (i==3) {
                    out<<decomposition(3);
                } else {
                    out<<"("<<decomposition(i-1)<<"+1)";
                }
                break;
            }
        } //for
    }
    
    return out.str();
}


int numones(const std::string& s) {
    int count=0;
    for (int i=0; i<s.size(); ++i) {
        if (s[i]=='1') count++;
    }
    return count;
}


int main() {
    int t;
    scanf("%i", &t);    //printf("%i\n", t);

    for (int count=0; count<t; ++count) {
        int v;
        scanf("%i", &v); //printf("\n%i\n", v);
        std::string representation = decomposition(v);
        if (numones(representation)>100) {
            printf("NIE\n");
        } else {
            printf("%s\n", representation.c_str());
        }
    }
    
    return 0;
}