提示: 欢迎访问OurACM平台。
Problem 1990 AntiAC II

Accept: 29    Submit: 127
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Usually, in programming contests all you wait is “AC” (abbreviation of AekdyCoin).We find that boring.

In this task we do the opposite. We will give you a string consists of only uppercase letters. You should remove some letters so that there is no “AC” in the result string. Return the result string with the longest length. If there is more than one string with the longest length, return lexicographically smallest one.

Input

In the first line there is an integer T, indicates the number of test cases. (T <= 10).In each case, there contains one string. The string is described in an compressed format. It is made of several compressors. A “compressor” is in the following format:

qx

q is a number( 0 < q <= 1 ,000,000,000)and x is a uppercase letter. It means q consecutive letter xs in the original uncompressed program. For example, ‘6K’ means ‘KKKKKK’ in the original program. So, if a compressed program is like:

2D7K1A1C

It actually is DDKKKKKKKAC after decompressed to original format.

You should note that two adjacent compressors must have different ‘x’.

The number of compressors of the string is no more than 1,000,000.

Output

For each case, output “Case idx: “ first where idx is the index of the test case start from 1, then output the result string in the described compressed format.

Sample Input

3 1A 1A1C1A 2A3C2B

Sample Output

Case 1: 1A Case 2: 2A Case 3: 3C2B

Source

FOJ有奖月赛-2010年11月

Submit  Back  Status  Discuss