“I Hate Parenthesis”, it was the phrase that Ana said during the class of arithmetic. She want a simple code made for yourself (of course) to “kick out” the parenthesis from particular expressions without break maths.

Input

The first line contains the number of test cases T. One expression per line from second to (T+1)-th line. Each expression contains only uppercase letters (each letter can appears once), operators (+, *) and parentheses (()). There are no spaces inside the expressions and no input line contains more than 80 characters.

Output

A single line per case. The line must contains the expression without parenthesis. If there is more than one addend then you must sort first the one with more factors. Addends with the same amount of factors must be sorted in alphabetic order. See the example for more details.

Example

Input:
2
C*(A+B)
(A+B+D*E)*C

Output:
A*C+B*C
C*D*E+A*C+B*C