Infix to Postfix Conversion

Given an infix expression containing single-letter operands (a-z) and the operators +, -, *, / along with parentheses ( ), convert the expression into its equivalent postfix (Reverse Polish) notation. The conversion should account for the standard operator precedence rules, where multiplication and division have higher precedence than addition and subtraction. Parentheses override the normal precedence rules.

For example, the infix expression "a+b*c" should be converted to "abc*+".

inputFormat

The input begins with an integer t representing the number of test cases. Each of the next t lines contains one infix expression. The expression will consist solely of lowercase alphabetic characters (operands), the operators +, -, *, /, and parentheses ( and ). There are no spaces in the input expressions.

outputFormat

For each test case, output the corresponding postfix expression on a new line.

5
a+b*c
(a+b)*c
a+b
a*(b+c)
(a+b)*(c+d)

abc*+
ab+c*
ab+
abc+*
ab+cd+*