T9 Spelling Solution:

#include <bits/stdc++.h>
using namespace std;

string translate(string s){
    string result("");
    char lookup[9] = {'2', '3', '4', '5', '6'};
    char c;
    char lastnum = 0;
    for(char c: s){
        char character;
        if(c == ' '){
            character = '0';
            if(lastnum == character){
                result.push_back(' ');
            }
            result.push_back(character);
            lastnum = character;
        } else {
            c -= 'a';
            if(c <= 14){
                int nums = c % 3 + 1;
                int index = c / 3;
                character = lookup[index];
                if(lastnum == character){
                    result.push_back(' ');
                }
                lastnum = character;
                while(nums--){
                    result.push_back(character);
                }
            } else {
                c -= 14;
                if(c <= 4){
                    character = '7';
                    if(lastnum == character){
                        result.push_back(' ');
                    }
                    lastnum = character;
                    while(c--){
                        result.push_back(character);
                    }
                } else {
                    if(c <= 7){
                        character = '8';
                        if(lastnum == character){
                            result.push_back(' ');
                        }
                        lastnum = character;
                        for(int i = 4; i < c; i++){
                            result.push_back(character);
                        }
                    } else {
                        character = '9';
                        if(lastnum == character){
                            result.push_back(' ');
                        }
                        lastnum = character;
                        for(int i = 7; i < c; i++){
                            result.push_back(character);
                        }
                    }
                }
            }
        }
    }
    return result;
}

int main(){
    // #ifndef TESTING
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    string line;
    getline(cin, line);
    int nCases = stoi(line);
    for(int i = 1; i <= nCases; i++){
        string line;
        getline(cin, line);
        cout << "Case #" << i << ": " << translate(line) << endl;
    }
    
    return 0;   
}