Shortening codes

Your task is to transform the expression with brackets into RPN form.

Priority: + - < * / < ^ < ( )

Input

The first line of the standard input contains one integer t (t<101) which is the number of test cases.

In each of the next t lines there is a string consisted of two-argument operators: +, -, *, /, ^, brackets ( ) and letters a-z (operands).

Output

For each test case print the expression in RPN form.

Example

Input:
4
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
((a-g)^l/c^h*(l^f-g^y)^i^j)
Output:
abc*+
ab+zx+*
at+bac++cd+^*
ag-l^ch^/lf^gy^-i^j^*

Information

You can win PenDrive 16 GB in this competition: contest.pl by solving a task similar to this. It's in Polish but it's just a task like this.

The difference is that the only language which is available is C. Also, if You want to win You have to have code which is not longer than 80 character.

The reward may not be very encouraging but it's to feel rivalry and satisfaction.

Edit (19.02.11): Competition has ended. Mateusz Gołębiewski from Poland has written code of length... 78 chars! Congratulations!

Notice

I made a mistake and exponentation in the task is left-associative while it should be right-associative.

Despite the mistake, I do not change tests so that all users who have already done this task didn't have to rewrite their programs.

I would like to apologise for the situation.

Special thanks to hallvabo who discovered this mistake.