Sofian Numbers
Source file: sofian.{c|cpp}
Input file: sofian.in
Output file: sofian.out

 
Sofia loves change. She gets bored easily especially when doing routine job. Being an accountant, she deals mostly (if not always) with calculations and numbers.
In the past, she worked with Arab numbers (1,2,..) but she wanted some change, so she decided to work in an Arab country where they use Indian numbers.
After a short time, she felt the need for novelty, so she opted for the Roman numbers.
After exhausting all these numbering systems, Sofia had a great idea, i. e : create her own numbering system (called Sofian numbers), so that she can change it whenever she feels the need for it!

The Sofian representation consists of using the first five letters of the alphabet to represent any given number between 1 and 100. A for 1, B for 5 , C for 10, D for 50 and E for 100.
To represent other values, a combination of these symbols is used. For example,
 
1 A 10 C 20 CC
2 AA 11 CA 30 CCC
3 AAA 12 CAA 40 AD
4 AB 13 CAAA 50 D
5 B 14 CAB 60 DA
6 BA 15 CB 70 DAA
7 BAA 16 CBA 80 DAAA
8 BAAA 17 CBAA 90 CE
9 AC 18 CBAAA 100 E
    19 CAC    
 

(Hint: Sofia was inspired by roman numbers).

You will help Sofia in her daily work by providing a solution that reads from a file an arithmetic expression (one at a time), evaluates it and provides the result.
Sofia is not interested in the result but in the number of A’s, B’s, C’s, D’s and E’s that are needed to represent numbers from 1 to result. An example is:

Result = 2 so we need to represent 1 and 2 so we only need 2 A’s .

Result = 20, we need to represent 1, 2,...,20 so we need 28 A’s, 10 B’s, 14 C’s, 0 D’s and 0 E’s . Input:
The first line in the file holds the number of n expressions.
The following lines each contain one arithmetic expression of the type: operand op operand such that op is * or + or – and operand is an integer ranging between 1 and 100. Ouput:

For each arithmetic expression in the file, the output file should contain one line containing the result (in decimal form) followed by the number of characters of each type required.
Assume that the result is always between 1 and 100.

Example Input:
4
1 + 0
2*1
30 - 10
90 + 9

Expected Output:
1: 1 A, 0 B, 0 C, 0 D, 0 E
2: 3 A, 0 B, 0 C, 0 D, 0 E
20: 28 A, 10 B, 14 C, 0 D, 0 E
99: 140 A, 50 B, 150 C, 50 D, 10 E