#2747 Getting the Digits

1 s   128 MB  

Description

You just made a new friend at an international puzzle conference, and you asked for a way to keep in touch. You found the following note slipped under your hotel room door the next day:

"Salutations, new friend! I have replaced every digit of my phone number with its spelled-out uppercase English representation ("ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE" for the digits 0 through 9, in that order), and then reordered all of those letters in some way to produce a string S. It's up to you to use S to figure out how many digits are in my phone number and what those digits are, but I will tell you that my phone number consists of those digits in nondecreasing order. Give me a call... if you can!"

You would to like to call your friend to tell him that this is an obnoxious way to give someone a phone number, but you need the phone number to do that! What is it?

Input

The first line of the input gives the number of test cases, TT test cases follow. Each consists of one line with a string S of uppercase English letters.

 

1 ≤ T ≤ 100.
A unique answer is guaranteed to exist.

 

3 ≤ length of S ≤ 2000.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string of digits: the phone number.

Sample Input

Sample Output

4
OZONETOWER
WEIGHFOXTOURIST
OURNEONFOE
ETHER
Case #1: 012
Case #2: 2468
Case #3: 114
Case #4: 3

Source

2016 Google Code Jam Round 1B