H. Fours Redux
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

May the Fours be with you!

On the unexplored planet of Dagobah, the Jedi Master Yoda is training the young Luke Skywalker in the ways of the Fours! To strengthen Luke's problem-solving skills, Yoda gives Luke some integers. For each integer $$$f_i$$$, Luke must generate an arithmetic expression that evaluates to that integer. Yoda gives Luke four rules to follow for each of his expressions.

1. The expression is a valid C-style arithmetic expression consisting only of operators + - * /, parentheses ( ), and the powerful number 4. The expressions must not contain spaces. Luke must treat each 4 as a separate value – he cannot append two fours together to make 44.

2. The expression must evaluate into the given integer result value $$$f_i$$$.

3. The number of operators in the expression is exactly one less than the number of fours. There can be many parentheses, as long as they match each other as they would in a valid C-style expression.

4. Luke must use the minimum possible amount of fours to make each expression, and his expressions must use 10 or less fours and use 100 characters or less, otherwise the expression is too powerful and may lead Luke to the dark side.

Yoda will provide Luke with a list of $$$n$$$ integers. For each integer $$$f_i$$$, Luke must provide a valid C-style expression fulfilling the above four rules that evaluates to $$$f_i$$$. If no expression can be made that fulfills the four rules, instead output IMPOSSIBLE.

For example, given the integer $$$64$$$, a possible expression is (4+4)*(4+4). However, $$$64$$$ can be calculated with only three 4s, with 4*4*4. Thus, (4+4)*(4+4) would not be an acceptable answer, but 4*4*4, (4*4)*4, ((4*(4)*4)) etc. would be acceptable.

Help Luke master the ways of the Fours!

Input

The first line of input contains the integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of integers Yoda will give to Luke.

Each of the next $$$n$$$ lines contains a single integer $$$f_i$$$ $$$(-10^9 \le f \le 10^9)$$$ — an integer for which Luke must generate an expression.

Output

For each integer $$$f_i$$$, output an expression that evaluates to it. If no expressions fulfill all four of Yoda's rules for that $$$f_i$$$, print IMPOSSIBLE. The generated expressions must not contain spaces.

Example
Input
8
4
0
21
42
-21
153
697
12321
Output
4
4-4
4*4+4/4+4
(((4/4+4)/4)+4)*(4+4)
4-(4+4+4*4+4/4)
((4+4)*4+4)*((4/(4*4))+4)
((4/(4*4))+4)*(4+((4+4)*(4+4*4)))
IMPOSSIBLE
Note

Note that there are many possible ways to generate these expressions.

$$$21$$$ may be obtained with 4*4+4+4/4, 4+4/4+4*4, etc. All of these would be accepted, as all use $$$5$$$ fours, which is the minimum number of fours required to produce $$$21$$$.

$$$153$$$ may also be obtained with (4*4+4/4)*(4+4+4/4) = 17*9 = $$$153$$$. Both use the minimum possible of $$$8$$$ fours, so both would be acceptable.