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

using namespace std;

string cover_with_parentheses(const string& val) {
  return (val.size() == 0 || (val.front()=='(' && val.back()==')')) ? val : "("+val+")";
}

vector<int> factorize(const int x) {
  vector<int> multi_factors;

  int d = 2, n = x;

  while(d*d <= n) {
    while(n % d == 0) {
      n /= d;
      multi_factors.push_back(d);
    }
    d++;
  }
  if(n > 1) multi_factors.push_back(n);

  return multi_factors;
}

string rep(int x) {
  if(x == 1)
    return "1";
  if(x == 2)
    return "1+1";
  
  string my_rep;
  auto factors = factorize(x);

  if(factors.size() == 1)
    my_rep = rep(x-1)+"+1";
  else {
    my_rep += cover_with_parentheses(rep(factors[0]));
    for(auto it = factors.begin()+1; it < factors.end(); it++)
      my_rep += "*" + cover_with_parentheses(rep(*it));
  }

  return my_rep;
}

void solve() {
  int n;
  scanf("%d", &n);

  printf("%s\n", rep(n).c_str());
}

int main() {

  int t;
  scanf("%d", &t);
  while(t --> 0) solve();

  return 0;
}