Phone Number Riddle (Small)

Interview

Time limit5sMemory limit512 MB

Summary

Given a shuffled string formed from the English words of a phone number's digits, recover the digits, which are guaranteed to be in ascending order.

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

Problem

"What's your phone number?"

"Write each digit of my phone number as an English word, shuffle the letters well, and you get OZONE TOWER."

"Sorry?"

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

"..."

The English words for the digits 0 to 9 are ZERO, ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, and NINE. Given the string the other person gave you, find the phone number.

Input

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

$1 \le T \le 100$ , and the length of $S$ is between 3 and 20, 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. The phone number is a string of digits in ascending order, and it may start with 0.

Hint

Arranging the letters of ZERO, ONE, and TWO gives OZONETOWER, so the answer to the first test case is 012.

Examples1

Example 1

Input

4
OZONETOWER
WEIGHFOXTOURIST
OURNEONFOE
ETHER

Expected output

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