string “weightfoxtourist” represents as 2468

problem.txt

Problem

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, T. T test cases follow.
Each consists of one line with a string S of uppercase English letters.

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.

Limits

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

3 ≤ length of S ≤ 20.

Large dataset

3 ≤ length of S ≤ 2000.

Sample


Input

Output

4
OZONETOWER
WEIGHFOXTOURIST
OURNEONFOE
ETHER

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

solution.cpp

#include <iostream>
#include <string.h>

using namespace std;

string sortToHeadOfSubstr(const string str, const string substr) {
  string copy = str;
  for (int i = substr.length() - 1; i >= 0; i --) {
    for (int j = 0; j < copy.length(); j ++) {
      if (substr[i] == copy[j]) {
        for (int k = j; k > 0; k --) {
          swap(copy[k], copy[k-1]);
        }
        break;
      }
    }
  }
  return copy;
}

string substrFromHead(const string str, const string sub) {
  string temp;
  if (sub.length() <= str.length()) {
    for (int i = 0; i < sub.length(); i++) {
      if (sub[i] == str[i]) {
        temp += str[i];
      }
    }
  }
  return temp;
}

string calculateRemainder(const string str, const string sub) {
  
  string sorted;
  string remainder;
  
  // sort string in order the substring to start from head
  sorted = sortToHeadOfSubstr(str, sub);
  
  // compute substring from sorted string
  string substrFromStr = substrFromHead(sorted, sub);
  
  // compute and return remainder
  if (sub == substrFromStr) {
    for (int i = sub.length(); i < sorted.length(); i++) {
      remainder += sorted[i];
    }
    return remainder;
  }
  // remainder is input string
  return str;
}

string digitsFromString(string str) {
  
  const int TOTAL = 10;
  string digits[TOTAL] = {
    "zero","one","two","three","four","five","six","seven","eight","nine"
  };
  
  string number;
  string remainder = str;
  
  string temp;
  
  for (int num = 0; num < TOTAL; num++) {
    temp = calculateRemainder(remainder, digits[num]);
    if (temp != remainder) {
      remainder = temp;
      number += to_string(num);
    }
  }
  
  return number;
}

int main(int argc, const char * argv[]) {
  
  cout << digitsFromString("ozonetower") << endl;
  
  return 0;
}