SCUSA Region ACM Balloon Logo ICPC Masthead
2010 ACM ICPC South Central USA Regional Programming Contest

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.


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.


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


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

Sample input


Sample output