In this task, we consider "one-expressions," which are expressions consisting only of ones, where the only allowed operations are addition and multiplication. In these expressions, there are no two (or more) adjacent ones—every two ones are separated by an operation. We can use parentheses in these expressions, and the order of operations is standard (multiplication has higher priority than addition).

For example, each of the following one-expressions has a value of 6: $(1+1)*(1+1+1)$, $(1+1+1)*(1+1)*1$, $((1+1)+1)*(1+1)$, $1+1+1+1+1+1$, $1+(1+(1+(1+(1+1))))$.

Write a program that, for a given positive integer $k$ ($k \le 10^9$), outputs a one-expression containing at most 100 ones that evaluates to $k$.

Formal definition of one-expressions: $1$ is a valid expression; If $W_1$ and $W_2$ are valid expressions, then each of the expressions: $W_1+W_2$, $W_1*W_2$, $(W_1+W_2)$, $(W_1*W_2)$ is a valid expression.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 100$), representing the number of test cases. The following $t$ lines describe the test cases. The $i$-th of these lines contains a single integer $k_i$ ($1 \le k_i \le 10^9$).

Output

Your program should output $t$ lines. If there is no one-expression containing at most 100 ones that evaluates to $k_i$, you should output NIE in the $i$-th line. Otherwise, the $i$-th line of the output should contain any such expression. The description of the expression should not contain any spaces.

Examples

Input 1

2
6
10

Output 1

(1+1)*(1+1+1)
1+1+1+1+1+1+1+1+1+1