Expressions

Arithmetic expressions are usually written with the operator between its two operands, which is called infix notation. For example, $(x + y) * (z - w)$ is an arithmetic expression in infix notation. It is easier, however, to write a program that evaluates an expression when the expression is given in postfix notation (also known as reverse Polish notation). In postfix notation, an operator is written after its two operands, each of which may itself be an expression. For example, x y + z w - * is the postfix form of the expression above. Note that parentheses are not needed.

A postfix expression can be evaluated with an algorithm based on a stack. A stack supports two operations:

1. push: insert a number at the top of the stack.
2. pop: remove the number from the top of the stack.

We scan the expression from left to right. When we meet a number, we push it onto the stack. When we meet an operator, we pop the top two numbers, apply the operator to them, and push the result back. Concretely, when we meet an operator $O$:

a := pop();
b := pop();
push(b O a);

After the whole expression has been processed, the single number left on the stack is the result.

Now suppose we use a queue instead of a stack. A queue also has push and pop, but their meaning differs:

1. push: insert a number at the back of the queue.
2. pop: remove the number from the front of the queue.

Rewrite the given postfix expression so that running the same algorithm with a queue yields the same result as the original expression evaluated with a stack.

The first line contains an integer $T$ ($T \le 200$). Each of the following $T$ lines contains one expression in postfix notation. Operators are written as uppercase letters and numbers as lowercase letters. The length of each expression is less than $10000$ characters.

For each expression, print an expression that produces the same result when evaluated with the queue-based algorithm instead of the stack-based one. To keep the answer unique, you may not assume that the operators are associative or commutative.