#include <iostream>
#include <map>
#include <string>
using namespace std;

const int MOD = 1013;
const int MAXQ = 10;

void solve(string spell, int code) {
    // map<hash, number of strings with this hash>
    map<int, long long> cnt;
    cnt[0] = 1;

    // table used to reconstruct solution,
    // prev[number of '?'][hash] = {char used, previous hash}
    int prev[MAXQ][MOD][2] = {};

    int q = 0;  // running number of '?'
    int k = 1;  // running power of 31
    for (int i = spell.size()-1; i >= 0; i--) {
        if (spell[i] != '?') {
            // update hash by throwing away known chars
            code -= k * spell[i] % MOD;
            if (code < 0) {
                code += MOD;
            }
        } else {
            map<int, long long> newcnt;
            for (char c = 'a'; c <= 'z'; c++) {
                map<int, long long>::iterator it = cnt.begin();
                for (; it != cnt.end(); ++it) {
                    // if we substitute '?' with char c,
                    // then new hash value will be:
                    int x = it->first + k * c % MOD;
                    if (x >= MOD) {
                        x -= MOD;
                    }
                    // and this new hash value can be reached from all
                    // previous ones by adding char c:
                    newcnt[x] += it->second;
                    prev[q][x][0] = c;
                    prev[q][x][1] = it->first;
                }
            }
            cnt.swap(newcnt);
            q++;
        }
        k = (k*31) % MOD;
    }

    if (cnt[code] != 1) {
        // print number of solutions if not unique
        cout << cnt[code];
        return;
    }

    // reconstruct unique solution
    for (int i = 0; i < spell.size(); i++) {
        if (spell[i] != '?') {
            continue;
        }
        q--;
        spell[i] = prev[q][code][0];
        code = prev[q][code][1];
    }
    cout << spell;
}

int main() {
    int T; cin >> T;
    for (int i = 0; i < T; i++) {
        int code; cin >> code;
        string spell; cin >> spell;
        cout << "Case #" << i+1 << ": ";
        solve(spell, code);
        cout << endl;
    }
    return 0;
}