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
#include <cstdio>
#include <vector>

const int MAX_K = 1000000; // 1 mln
std::vector<int> unary;
std::vector<int> track;

void init() {
	std::vector<bool> primes;
	unary.resize(MAX_K + 1);
	primes.resize(MAX_K + 1, true);
	track.resize(MAX_K + 1);
	primes[0] = primes[1] = false;
	for(int i = 0; i <= MAX_K; ++i) {
		unary[i] = i;
		track[i] = i - 1;
	}
	int upto = MAX_K / 2;
	for(int p = 3; p <= upto; ++p) {
		if(unary[p - 1] + 1 < unary[p]) {
			unary[p] = unary[p - 1] + 1;
			track[p] = p - 1;
		}
		// TODO: can be skipped?
		if(!primes[p]) { 
			continue;
		}
		for(int k = 2; k <= p; k++) {
			int i = k * p;
			if(i > MAX_K) {
				break;
			}
			if(unary[k] + unary[p] < unary[i]) {
				unary[i] = unary[p] + unary[k];
				track[i] = p;
			}
			primes[i] = false;
		}
	}
	for(int p = upto + 1; p <= MAX_K; ++p) {
		if(unary[p - 1] + 1 < unary[p]) {
			unary[p] = unary[p - 1] + 1;
			track[p] = p - 1;
		}
	}
}

void print_expr(int k) {
	if(k == 1) {
		printf("1");
		return;
	}
	int from = track[k];
	if(k - from == 1) {
		printf("(1+");
		print_expr(from);
		printf(")");
	}
	else {
		printf("(");
		print_expr(from);
		printf("*");
		print_expr(k / from);
		printf(")");
	}
}

void solve(int k) {
	if(k <= MAX_K) {
		print_expr(k);
	}
	else {
		int fact = k / 1000;
		print_expr(fact);
		printf("*");
		print_expr(1000);
		int rest = k - 1000 * fact;
		if(rest > 0) {
			printf("+");
			print_expr(rest);
		}
	}
	printf("\n");
}

int main() {
	int t, k;
	init();
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &k);
		solve(k);
	}
}