Description

" Please don't CoCo everywhere. "

— JJ Lin, If you're not trendy, you don't have to spend money

Capybara and CabiCabi have recently made a groundbreaking discovery! The tea shop CoCo near NTHU gives you a discount coupon after every purchase, which allows you to buy an 80 NTD coffee for just 25 NTD on your next visit, and that purchase will instantly give you another coupon — they have basically found an endless loop of 25 NTD coffee!

Such unbelievably cheap prices make them unable to resist buying a cup every time they pass by. However, the cost still adds up over time, so they must come up with a more cost-effective strategy. Capybara suggested seeking help from Lizard Tom! It is rumored that Lizard Tom has recently been studying a software called "cocos creator". Although they have no idea what it is actually used for, it sounds like something capable of generating a massive amount of CoCo.

---

Lizard Tom has something he'd like to say: he indeed possesses the technology to create CoCo, but he has no control over the exact amount he produces.

Specifically, if CabiCabi gives him an order of cups of CoCo, the actual number of cups Lizard Tom produces will be , which is defined as follows:

L... L for Lizard! Huh? What is a function? I always predict the amount of generated CoCo by guessing!

As everyone knows, Lizard Tom is terrible at math because he never pays attention during dyy's classes. To prevent the tragedy of "CoCo everywhere" from happening, please write a program to help Capybara and CabiCabi calculate exactly how many cups of CoCo Lizard Tom will ultimately produce when they place an order for cups.

Hint

• is equivalent to , as long as there's no division in your eqution, you can take mod at anytime you want
• is SUPER BIG. You don't need to worry about large number calculations, because Python will handle it for you. But obviously, creating a list with size isn't a good idea. Furthermore, you wouldn't want to repeatedly calculate known values.
• If you receive RE or MLE due to Floating-point accuracy problem, try using // instead of math.floor + /

Input

The first line contains a single positive integer T, representing the number of testcases

Each testcase contains a single positive integer , representing the number of CoCo cups originally ordered from Lizard Tom.

Constraints

Subtasks

• For Testcases 1 ~ 3,
• For Testcases 4 ~ 6,
• For Testcases 7 ~ 10,

Output

For each testcase, print a single integer in a new line, representing the number of CoCo cups ultimately produced by Lizard Tom.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Capybara's friend CABI-bara is a chemist who is currently learning about organic chemistry. His work is to analyze various elements. However, the machine in his lab is malfunctioning and can only output complex chemical formulas. He needs the students' help to analyze the elements!

Given a chemical formula (a string), please parse all the chemical elements inside and calculate the total amount of each element.

Finally, you MUST output the results sorted by their Atomic Number in ascending order.

The chemical formula strictly follows these rules:

• Element Symbols: An element symbol always starts with exactly one uppercase English letter, followed by zero or more lowercase English letters (e.g., C, H, O, Na, Cl).
• Quantity Indicators: If a number directly follows an element symbol, it represents the quantity of that element (e.g., in H2O, the quantity of H is 2). If there is no number, the quantity is implicitly 1 (e.g., in H2O, the quantity of O is 1).
• The number can be a multi-digit integer.
• Parentheses Multiplication: The formula may contain parentheses (). A closing parenthesis ) will always be immediately followed by a number , meaning the quantities of all elements inside the parentheses are multiplied by . For example, Ca(OH)2 contains 1 Ca, 2 O, and 2 H. Parentheses are guaranteed to be valid, balanced, and can be nested.

To help you sort the elements, CABI-bara has provided the periodic table used in this homework.

(Note: Although the chart shows the entire periodic table, CABI-bara guarantees that you only need to handle the first 36 elements, from Hydrogen (1) to Krypton (36).)

Input

The input contains only one line, which is a valid chemical formula string .

• All quantity numbers and the final count of each element will fit in a standard 32-bit signed integer.
• The string only contains uppercase letters, lowercase letters, digits, (, and ).
• It is guaranteed that all elements appearing in the test cases have an atomic number .

Output

Output multiple lines. For each element present in the formula, output in the format:
Element: Quantity.
The output lines MUST be sorted in ascending order of their Atomic Numbers.

Sample Input  Download

Sample Output  Download

Tags

Discuss