Problem F
Forming Expressions

Prof. Adi once posted the following message on the NUS ICPC Discord server:

Inspiration for IOI: \[ 10+9 \times 8 \times (7+6+5+4+3+2+1) = 2026 \] For each year, find the shortest consecutive numbers from $1$ together with operations $+$ and $\times $ (and parentheses to disambiguate) that forms the number.

Dr. Eldon pointed out:

Wouldn’t this mean that some numbers are impossible to generate?

e.g. the year $4$.

To which, prof. Adi amended the statement:

Output $-1$ if impossible.

rama_pang is writing competitive-programming-themed sci-fi fanfic and consider what the expression would looks like in the far future, say, in year $10^{19}$. Because computers nowadays are far less powerful than that in year $10^{19}$, you don’t need to find the shortest expression, merely some short-enough expression.

Formally: given an integer $N$ such that $N = 2026$ or $10^{19} \leq N < 2^{64}$, find an expression consisting of only binary addition, multiplication, parentheses, and the numbers $a$, $a-1$, $\dots $, $1$ in that order where $a$ is a positive integer less than $200$, that evaluates to $N$.

By the way, the checker is not just Python eval, so don’t try to submit a program that prints out something like __import__('sys').exit(42).

Input

The first line of input contains an integer $q$ ($1 \leq q \leq 200$), the number of queries you need to handle.

Each of the following $q$ lines contain an integer $N$ as above.

Output

For each query, output an expression satisfying the conditions above on a separate line that evaluates to $N$, or $-1$ if there is no such expression. Note that spaces are not allowed in an expression, and expressions are restricted to $5000$ characters, which is actually easy to satisfy (since $a < 200$) unless you output a lot of redundant parentheses.

Notes

Unary addition is not allowed. For example, 2+(+1) is not a valid output.

Subtraction is not allowed. For example, 2-1 is not a valid output.

Proclaimer

Names, characters, events, and incidents are mostly accurate, or plausibly so. Any resemblance to actual persons, living or dead, or actual events is purely intentional.

1
2026

10+9*8*(7+6+5+4+3+2+1)