Infix to Postfix Expression Conversion

This problem requires you to convert an infix mathematical expression into its equivalent postfix (Reverse Polish) notation. The input expression will contain single-digit operands and the operators +, -, *, /, and ^ as well as parentheses. Note that operator precedence is defined as follows: $$+,-:1$$, $$*,/:2$$, and $$^:3$$. The exponentiation operator is right-associative while the other operators are left-associative. Use the Shunting Yard algorithm to perform the conversion.

For example, the infix expression "3+4*2/(1-5)^2^3" converts to the postfix expression "342*15-23^^/+".

inputFormat

The first line of input contains a single integer n, representing the number of test cases. Each of the next n lines contains one infix expression (without spaces) composed of digits and the operators mentioned above.

outputFormat

For each test case, output a single line containing the postfix expression corresponding to the given infix expression.

1
3+4*2/(1-5)^2^3

342*15-23^^/+