408734: GYM103274 L Leonel and the powers of two

L. Leonel and the powers of twotime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Leonel is solving exponentiation problems, he has become really good to calculate powers of two. Several times Leonel has impressed his friends and teacher showing his skills answering what is the value for the $$$k$$$-th power of two ($$$2^k$$$), with really large values for $$$k$$$.

To make things more challenging to Leonel, his teacher has requested to him, instead of calculating the value for $$$2^k$$$, to write the result in the following notation:

• 2 if $$$k = 1$$$
• $$$(2*2^{k-1})$$$ if $$$k$$$ is an odd number
• $$$(2^{\frac{k}{2}})^2$$$ if $$$k$$$ is an even number

Leonel will have to repeat the process until no more changes can be done to the current notation. For example if $$$k = 5$$$, then the first time Leonel does the notation he will write $$$(2*2^4)$$$. Leonel can change the notation replacing $$$2^4$$$ with $$$(2^{\frac{4}{2}})^2 = (2^2)^2$$$, resulting in : $$$(2*(2^2)^2)$$$, Leonel can change this notation replacing $$$2^2$$$ with $$$(2^{\frac{2}{2}})^2$$$, after this change the notation will be: $$$(2*((2^1)^2)^2)$$$, one last change can be done to the notation changing $$$2^1$$$ with $$$2$$$, which will result in $$$(2*((2)^2)^2)$$$, since no more changes can be done, Leonel has found the answer for $$$k = 5$$$.

Leonel is certain it will take more time for him to write in this notation than calculating the power, that is why he decided to ask for your help to write a computer program so he can copy the notation from the result of your program to his notebook. Given the value of $$$k$$$ write a program that prints $$$2^k$$$ in the notation described by Leonel's teacher.

Input

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$), the number of test cases. Each of the next $$$T$$$ lines contains a single integer $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$), representing the power of two Leonel has to write in his teacher's notation.

Output

For each test case in the input print the result of the final notation Leonel will get.

ExampleInput

5
1
2
3
4
5

Output

2
(2)^2
(2*(2)^2)
((2)^2)^2
(2*((2)^2)^2)