Phone Number Riddle (Large)

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.