Sum of Products

Mathematicians, unlike programmers, write expressions using single lower-case letters as variables. Addition is written with a plus sign +, and multiplication is written by placing variables or sub-expressions next to each other with no symbol between them. Multiplication is performed before addition, unless the addition is wrapped in parentheses.

In this problem an expression is built only from variables, addition, multiplication, and parentheses. There are no other symbols: no spaces, division, subtraction, or numerals appear in the input or the output. For example, the following are all valid expressions:

a+b+c
xyz
xyz+ab+cd
(a+b)(c+d)e

For each expression you must apply the laws of algebra (the distributive law) to remove every parenthesis, turning it into an equivalent sum of products. For example, (a+b)(c+d)e is equivalent to ace+ade+bce+bde.

Like terms are never combined; since there are no numerals in the output this is impossible anyway. Every term produced by fully expanding the expression is kept, including duplicates. To make the answer unique, the order of variables inside each term and the order of the terms follow the canonical form defined in the Output section.

The first line contains an integer $n$, the number of expressions. Each of the next $n$ lines contains one valid expression as described above. No expression line is longer than $100$ characters.

Print $n$ lines. For the expression on line $i$ of the input, print its fully expanded sum of products, without parentheses, on line $i$ of the output, using the following canonical form so that the answer is unique:

• Apply the distributive law until no parentheses remain, expanding the expression into a sum of terms (each term is a product of variables).
• Do not combine like terms: every term produced by the expansion is kept, including duplicates.
• Within each term, list its variables in ascending alphabetical order.
• List the terms in ascending lexicographical (dictionary) order, joined with +.

For example, (a+b)(c+d)e expands into the four terms ace, ade, bce, bde; each term is already alphabetical and the terms are already in dictionary order, so the answer is ace+ade+bce+bde.