E - Odio los paréntesis

Time limit: 2 s
Memory limit: 32 MiB
Languages: C, C++, Java, Pascal, ... (details)

“Odio los paréntesis” fue la frase que dijo Ana durante la clase de aritmética. Ella dice que tiene demasiadas complicaciones con la asignatura y cuando encuentra además, muchos cálculos anidados, entonces las cosas se complican aún más. Por eso, ella quiere que hagas un programa que le ayude a eliminar los paréntesis de una expresión sin violar la matemáticas básica.

Input

La primera línea contiene la cantidad de casos de pruebas $T$. Una expresión por línea desde la segunda hasta la $(T + 1)$-esima línea. Cada expresión contiene solo letras en mayúsculas del alfabeto inglés (Cada letra aparece como máximo una vez en cada expresión), operadores ($\texttt{+}$, $\texttt{*}$) y paréntesis ($\texttt{()}$). No hay espacios dentro de la expresión y ninguna línea contiene más de $80$ caracteres.

Output

Una línea por caso. La línea debe contener la expresión sin paréntesis. Si hay más de un sumando entonces Ana quiere el sumando con mayor cantidad de factores. Dos sumandos con la misma cantidad de factores debe listarse primero la alfabéticamente menor. Ver ejemplos para más detalles.

Sample test(s)

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