Phone Number Riddle (Large)

Interview

Time limit5sMemory limit512 MB

Summary

A shuffled concatenation of the English words for a phone number's digits is given; recover the digits, which are in ascending order.

Level: Medium5 of 10
Topics: String, Hash map, Greedy, Math
Solved: No attempts yet

Problem

"What is your phone number?"

"If you replace each digit of my phone number with its English word and shuffle the letters well, you get OFFER EN NOXIOUS NEON OVERUSE."

"Sorry?"

"Also, the digits of my phone number are sorted in ascending order."

"..."

Each digit is replaced by one of ZERO, ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, or NINE. The words are concatenated and the letters are then shuffled into an arbitrary order. Given the resulting string S, recover the original phone number.

Input

The first line contains the number of test cases $T$ . Each of the next $T$ lines contains one string $S$ given by the other person. $S$ consists of uppercase English letters only.

$1 \le T \le 100$ , and the length of $S$ is between 3 and 2000, inclusive. Every test case has exactly one answer.

Output

For each test case, print one line in the form Case #x: y, where $x$ is the test case number and $y$ is the phone number. $y$ lists the digits of the phone number in ascending order and may start with 0.

Hint

Rearranging the letters of ONE ONE ONE FOUR FOUR SIX SEVEN gives OFFERENNOXIOUSNEONOVERUSE. So the phone number for this string is 1114467.

Examples1

Example 1

Input

4
OZONETOWER
WEIGHFOXTOURIST
OURNEONFOE
ETHER

Expected output

Case #1: 012
Case #2: 2468
Case #3: 114
Case #4: 3