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
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class jed {
	
	private static final int MAX_N = 1000000000;
	Map<Integer, String> cache = new HashMap<>();
	Set<Integer> primes = new HashSet<>();
	List<Integer> primesList = new ArrayList<Integer>();
	
	public static void main(String[] args) throws Exception {
		jed solver = new jed();
		solver.solve();	
	}
	
	public void prepare() {
		byte[] arr = new byte[MAX_N];
		for (int i=2; i<MAX_N; i++) {
			if (arr[i] == 0) {
				primes.add(i);
				primesList.add(i);
				int j = i * i;
				while (j < MAX_N) {
					arr[j] = 1;
					j *= i;
				}
			}
		}
		cache.put(1, "1");
	}
	
	public void solve() throws FileNotFoundException {
		Scanner sc = new Scanner(System.in);
		int cases = sc.nextInt();
		for (int i=0; i<cases; i++) {
			System.out.println(this.solveOne(sc.nextInt()));
		}
		sc.close();
	}
	
	public String solveOne(int number) {
		if (cache.containsKey(number)) {
			return cache.get(number);
		}
		if (primes.contains(number)) {
			String sol = solveOne(number - 1);
			sol = "1+(" + sol + ")";
			cache.put(number, sol);
			return sol;
		} else {
			int n = number;
			List<Integer> factors = new ArrayList<>();
			for (int i=0; i<primesList.size(); i++) {
				while (n % primesList.get(i) == 0) {
					factors.add(primesList.get(i));
					n /= primesList.get(i);
				}
				if (n == 1) {
					break;
				}
			}
			StringBuilder sb = new StringBuilder();
			for (int f : factors) {
				sb.append("(").append(solveOne(f)).append(")*(");
			}
			String sol = sb.toString();
			sol = sol.substring(0, sol.length() - 2);
			cache.put(number, sol);
			return sol;
		}
	}
}