B - Leonel and the powers of two

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 kk-th power of two (2^k2k), with really large values for kk.

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

• 2 if k = 1k=1
• (2*2^{k-1})(2∗2k−1) if kk is an odd number
• (2^{\frac{k}{2}})^2(22k​)2 if kk 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 = 5k=5, then the first time Leonel does the notation he will write (2*2^4)(2∗24). Leonel can change the notation replacing 2^424 with (2^{\frac{4}{2}})^2 = (2^2)^2(224​)2=(22)2, resulting in : (2*(2^2)^2)(2∗(22)2), Leonel can change this notation replacing 2^222 with (2^{\frac{2}{2}})^2(222​)2, after this change the notation will be: (2*((2^1)^2)^2)(2∗((21)2)2), one last change can be done to the notation changing 2^121 with 22, which will result in (2*((2)^2)^2)(2∗((2)2)2), since no more changes can be done, Leonel has found the answer for k = 5k=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 kk write a program that prints 2^k2k in the notation described by Leonel's teacher.

Input

The first line of input contains a single integer TT (1 \leq T \leq 10^41≤T≤104), the number of test cases. Each of the next TT lines contains a single integer kk (1 \leq k \leq 10^{18}1≤k≤1018), 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.

Sample 1

Inputcopy	Outputcopy
5 1 2 3 4 5	2 (2)^2 (2*(2)^2) ((2)^2)^2 (2*((2)^2)^2)

 分析,运用递归,使用string定义的函数,如果k=1返回1,奇数返回(2*"+solve(k-1)+")偶数返回("+ solve(k/2)+")^2

#include <iostream>
 
using namespace std;
 
string solve(long long k){
    if(k==1){
        return "2";
    }
    if(k%2==1){
        return "(2*"+solve(k-1)+")";
    }
    else if(k%2==0){
        return "("+ solve(k/2)+")^2";
    }
}
int main(){
    int t;
    long long k;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&k);
        cout<<solve(k)<<endl;
    }
 
}