FERT21_1 - I Hate Parenthesis

“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

Added by:leandro
Date:2012-03-05
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:-

hide comments
2016-04-11 17:13:15
Can an expresion have more than one letter, like ABC*(E+D)*FG, and if yes do we turn it into A*B*C*D*F*G+A*B*C*E*F*G or ABC*D*FG+ABC*E*FG?
2016-04-05 11:16:06 Vilius Pranckaitis
Moved to forum: http://discuss.spoj.com/t/wa-on-fert21-1/14175

Last edit: 2016-04-05 11:53:23
2012-05-30 13:33:38 :D
"Each expression contains only uppercase letters (each letter can appears once), operators(+,*) and parentheses (())".

All conditions are met. Why would it be invalid?
2012-05-30 11:50:51 Goldie
@Leandro Castillo Valdes

Is (A+B)*(C+D) is valid test case? please help.. thanks in adv
2012-03-23 06:52:00 :D
Thanks!
2012-03-23 01:21:12 leandro
Problem is fixed and rejudged now.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.