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

#define sc(a) scanf("%d",&a)
#define scll(a) scanf("%I64d",&a)
#define scs(a) scanf(" %s",a)
#define scc(a) scanf(" %c",&a)

const int MAX = 1e5+6;
const int INF = 2e9+5;
const long long MOD = 1e9+7;

long long power (long long a ,long long e ,long long mod)
{
	if (e == 0)
		return 1ll;
	if (e == 1)
		return a % mod;
	if (e & 1)
		return ((a%mod) * power(a,e-1,mod))%mod;
	else
	{
		long long tmp = power(a,e/2,mod);
		return (tmp*tmp)%mod;
	}
}

long long gcd(long long x,long long y)
{
    return __gcd(x,y);
}

long long lcm(long long x,long long y)
{
    return (x*y)/gcd(x,y);
}

char in[10005];
int len,n;
long long dp[10005][1020];

long long solve(int id = 0,int code = 0)
{
    if(id == len)
        return code == n;

    long long &ret = dp[id][code];
    if(ret != -1)
        return ret;
    ret = 0;
    if(in[id] == '?')
    {
        for(int i=0;i<26;++i)
            ret += solve(id+1,(code * 31 + ('a'+i)) % 1013);
    }
    else
    {
        int tmp = code;
        int i;
        for(i=id;i<len;++i)
            if(in[i] != '?')
                tmp = (tmp * 31 + in[i]) % 1013;
            else
                break;
        if(i == len-1 && in[i] != '?')
            ++i;
        ret += solve(i,tmp);
    }

    return ret;
}

void print(int id = 0,int code = 0)
{
    if(id == len)
        return;

    long long ret = solve(id,code);

    if(in[id] == '?')
    {
        for(int i=0;i<26;++i)
        {
            if(solve(id+1,(code * 31 + ('a'+i)) % 1013) == ret)
            {
                putchar('a'+i);
                print(id+1,(code * 31 + ('a'+i)) % 1013);
                break;
            }
        }
    }
    else
    {
        int tmp = code;
        int i;
        for(i=id;i<len;++i)
            if(in[i] != '?')
                putchar(in[i]),tmp = (tmp * 31 + in[i]) % 1013;
            else
                break;
        if(i == len-1 && in[i] != '?')
            ++i;
        print(i,tmp);
    }
}

int main()
{
    int T;
    sc(T);
    for(int i=1;i<=T;++i)
    {
        sc(n);
        scs(in);
        len = strlen(in);
        memset(dp,-1,sizeof dp);
        printf("Case #%d: ",i);
        if(solve() != 1ll)
            printf("%lld\n",solve());
        else
            print(),puts("");
    }

	return 0;
}