시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 38 | 24 | 20 | 83.333% |
Let us define 1-expressions to be the numeric expressions containing only ones, addition signs, multiplication signs and parentheses. In such expressions no two digits can be neighboring -- every two ones must be separated by an operator. We follow the usual order of evaluating the expressions -- for example, the multiplication has larger priority than the addition.
For example, each of the following 1-expressions evaluates to 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))))
.
Formally, the following grammar describes all the correct 1-expressions $E$:
E ::= 1 | E+E | E*E | (E+E) | (E*E)
Write a program that, given an integer $k$ ($k \le 10^9$), outputs a 1-expression evaluating to $k$ that contains at most 100 ones.
The first line of the input contains a single integer $t$ ($1 \le t \le 100$) -- the number of testcases.
Each of the following $t$ lines describe a single testcase. The $i$-th of these lines describes the $i$-th test and contains a single integer $k_i$ ($1 \le k_i \le 10^9$).
You should output exactly $t$ lines.
If there is no 1-expression evaluating to $k_i$ and containing at most 100 ones, you should output NO
in the $i$-th line. Otherwise, the line should contain the required solution. You should not print any spaces inside the expression. If there is more than one correct solution, print any.
2 6 10
(1+1)*(1+1+1) 1+1+1+1+1+1+1+1+1+1