E - Chemistry

The chemical formula of a molecule describes its atomic makeup. A chemical formula is written as a sequence of either elements or subgroups of chemicals in parenthesis. An element or subgroup can have an optional multiplier suffix (always between 2 and 9). Elements are written in the shorthand notation of the periodic table, where all names have the form of an upper case letter, followed by between zero and two lower case letters.

For example, H2O has two hydrogen (H) and one oxygen (O) atoms, and (AlC2)3Na4 contains 3 aluminum (Al), 6 carbon (C) and 4 sodium (Na) atoms.

Input

The data file contains one line with N an integer where N is an integer between one and 1000. The next N lines will have chemical formulas, one per line. Max line length will be 132 characters.

Output

The atomic decomposition of each chemical in the form of a sum as in

2H+O
3Al+6C+4Na

The atoms are written in alphabetical order, and a count of 1 is written with the 1 implied.

Sample input

3
H2O
(AlC2)3Na4
((MO)7(N))9I6

Sample output

2H+O
3Al+6C+4Na
6I+63M+9N+63O