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
114
115
116
117
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class jed {

	private static final int MAX_PRIME = 31625;

	private static Set<Integer> primes = new TreeSet<Integer>();
	private static Map<Integer, Result> results = new TreeMap<>();

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		generatePrimes();

		int t = in.nextInt();
		for (int it = 0; it < t; it++) {
			int k = in.nextInt();
			Result result = getResult(k);
			if(result.getSize()>100)
				System.out.println("NIE");
			else
				System.out.println(result.getOnes());
		}
		in.close();
	}

	private static void generatePrimes() {
		boolean isNotPrime[] = new boolean[MAX_PRIME];
		for (int i = 2; i * i < MAX_PRIME; i++) {
			for (int j = i; i * j < MAX_PRIME; j++)
				isNotPrime[i * j] = true;
		}
		for (int i = 2; i < MAX_PRIME; i++)
			if (!isNotPrime[i])
				primes.add(i);
	}

	private static Result getResult(int n) {
		if (n == 1)
			return new Result("1", 1);
		if (n == 2)
			return new Result("1+1", 2);
		if (n == 3)
			return new Result("1+1+1", 3);
		if (n == 4)
			return new Result("1+1+1+1", 4);
		if (n == 5)
			return new Result("1+1+1+1+1", 5);
		List<Integer> factors = getPrimeFactors(n);
		if (factors.size() == 1) {
			Result res = results.get(Integer.valueOf(n));
			if (res != null)
				return res;
			Result prev = getResult(n - 1);
			StringBuilder sb = new StringBuilder();
			sb.append("(");
			sb.append(prev.getOnes());
			sb.append(")+1");
			res = new Result(sb.toString(), prev.getSize() + 1);
			results.put(Integer.valueOf(n), res);
			return res;
		}
		StringBuilder sb = new StringBuilder();
		int size = 0;
		for(Integer factor:factors) {
			Result res = getResult(factor);
			if(size>0)
				sb.append("*");
			sb.append("(");
			sb.append(res.getOnes());
			sb.append(")");
			size+=res.getSize();
		}
		return new Result(sb.toString(), size);
	}

	private static List<Integer> getPrimeFactors(int n) {
		int sqrt = (int) Math.floor(Math.sqrt(n));
		int tmp = n;
		int k = 2;
		List<Integer> res = new LinkedList<>();
		while (tmp > 1 && k <= sqrt) {
			while (tmp % k == 0) {
				res.add(k);
				tmp /= k;
			}
			++k;
		}
		if (tmp > 1)
			res.add(tmp);
		return res;
	}

}

class Result {
	String ones;
	int size;

	public Result(String ones, int size) {
		this.size = size;
		this.ones = ones;
	}

	public String getOnes() {
		return ones;
	}

	public int getSize() {
		return size;
	}
}