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
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class jed {
	
	static X[] arr;
	
	public static class X {
		char type;
		int val, ones;
		X lewy, prawy;
		
		static X one = new X('*', 1, 1, null, null);
		
		public X(char type, int val, int ones, X lewy, X prawy) {
			this.type = type;  this.val = val;  this.ones = ones;	this.lewy= lewy; this.prawy= prawy;
		}
		public static X add(int val, X lewy, X prawy) { return new X('+', val, lewy.ones + prawy.ones, lewy, prawy);}
		public static X mul(int val, X lewy, X prawy) { return new X('*', val, lewy.ones + prawy.ones, lewy, prawy);}
		
		public String toString() {
			if (val == 1) return "1";
			return "(" + lewy.toString() + type + prawy.toString() + ")";
//			if (type == '+') return lewy.toString() + type + prawy.toString();
//			return "(" + lewy.toString() + ")" + type + "(" + prawy.toString() + ")";
		}
	}

	public static X better(X xx, X x) { return x.ones < xx.ones  ? x : xx; }
	
	public static void main(String[] args) throws Exception {
		io();
	}

	public static void fillArr() {
		arr[1] = X.one;
		for (int i = 2; i<arr.length; i++) {
			X best = X.add(i, arr[1], arr[i-1]);
			for (int j = 2; j*j<=i; j++) 
				if (i % j == 0) 
					best = better(best, X.mul(i, arr[j], arr[i/j]));
//			for (int j = 1; j+j<=i; j++) // mozna tylko do polowy isc
//				best = better(best, X.add(i, arr[j], arr[i-j]));
//			System.out.println(""+i+"\t"+best.ones+"\t"+best.lewy.val + " " + best.type + " " + best.prawy.val + "\t" + best);
			arr[i] = best;
		}
	}
	
	public static void io() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Tokenizer.stoint(br.readLine());
		int ns[] = new int[t];
		int max = 0;
		for (int i = 0; i<ns.length; i++) {
			ns[i] = Tokenizer.stoint(br.readLine());
			max = Math.max(max, ns[i]);
		}
		arr = new X[max+1];
		fillArr();
		for (int n : ns) {
			if (arr[n].ones > 100) {
				System.out.println("NIE");
			} else {
				System.out.println(arr[n]);
			}
		}
	}

	public static class Tokenizer {
		public static int[]	stoints(String line) {
			String[] ss = line.split(" ");
			int[] ret = new int[ss.length];
			for (int i = 0; i<ss.length; i++) {
				ret[i] = Integer.valueOf(ss[i]);
			}
			return ret;
		}
		public static int stoint(String s) {
			return stoints(s)[0];
		}
	}

}