astein

#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <cstring>

using namespace std;

char a[115][115];
int totcnt;
int K;
int ret;

int dx[4] = {0, 1, 1, 1};
int dy[4] = {1, -1, 0, 1};
int s4, s3, s2;
int n, m;

map<pair<int, string>, double> pmap;
string S;
int KK;

void go(int k) {
    if (k == S.size()) {
        totcnt++;
        char mid = S[S.size() / 2];
        if (S.find(string(S.size() / 2 + 1, mid)) != string::npos) {
            ret++;
        }
        return;
    }
    if (S[k] == '?') {
        for (int i = 1; i <= KK; ++i) {
            S[k] = '0' + i;
            go(k + 1);
            S[k] = '?';
        }
    } else {
        go(k + 1);
    }
}

void pcalc(int K, string s) {
    if (pmap.count(make_pair(K, s)) > 0) return;
    S = s;
    KK = K;
    totcnt = 0;
    ret = 0;
    go(0);
    pmap[make_pair(K, s)] = ret * 1.0 / totcnt;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int cn = 1; cn <= T; ++cn) {
        totcnt = 0;
        int k;
        scanf("%d%d%d%d%d%d", &n, &m, &k, &s4, &s3, &s2);
        K = k;
        ret = 0;
        memset(a, 0, sizeof(a));
        for (int i = 0; i < n + 6; ++i)
            for (int j = 0; j < m + 6; ++j)
                a[i][j] = '0';
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                scanf(" %c", &a[i + 3][j + 3]);
            }
        n += 6, m += 6;
        for (int i = 3; i < n - 3; ++i) {
            for (int j = 3; j < m - 3; ++j) {
                for (int k = 0; k < 4; ++k) {
                    string s = "";
                    for (int l = -3; l <= 3; ++l) {
                        s += a[i + l * dx[k]][j + l * dy[k]];
                    }
                    char mid = a[i][j];
                    if (mid == '?') {
                        string s1 = s, s2 = s.substr(1, 5), s3 = s.substr(2, 3);
                        for (int l = 1; l <= K; ++l) {
                            s1[3] = '0' + l;
                            s2[2] = '0' + l;
                            s3[1] = '0' + l;
                            pcalc(K, s1);
                            pcalc(K, s2);
                            pcalc(K, s3);
                        }
                    } else {
                        pcalc(K, s);
                        pcalc(K, s.substr(1, 5));
                        pcalc(K, s.substr(2, 3));
                    }
                }
            }
        }

        ret = 0;
        double sol = 0.0;
        for (int i = 3; i < n - 3; ++i) {
            for (int j = 3; j < m - 3; ++j) {
                string s[4];
                char mid = a[i][j];
                for (int k = 0; k < 4; ++k) {
                    s[k] = "";
                    for (int l = -3; l <= 3; ++l) {
                        s[k] += a[i + l * dx[k]][j + l * dy[k]];
                    }
                }
                if (mid == '?') {
                    double rr = 0, r4 = 0, r3 = 0, r2 = 0;
                    for (int k = 1; k <= K; ++k) {
                        s[0][3] = s[1][3] = s[2][3] = s[3][3] = '0' + k;
                        double p4s1 = pmap[make_pair(K, s[0])];
                        double p4s2 = pmap[make_pair(K, s[1])];
                        double p4s3 = pmap[make_pair(K, s[2])];
                        double p4s4 = pmap[make_pair(K, s[3])];
                        double p4 = 1.0 - (1.0 - p4s1) * (1.0 - p4s2) * (1.0 - p4s3) * (1.0 - p4s4);
                        double p3s1 = pmap[make_pair(K, s[0].substr(1, 5))];
                        double p3s2 = pmap[make_pair(K, s[1].substr(1, 5))];
                        double p3s3 = pmap[make_pair(K, s[2].substr(1, 5))];
                        double p3s4 = pmap[make_pair(K, s[3].substr(1, 5))];
                        double p3 = 1.0 - (1.0 - p3s1) * (1.0 - p3s2) * (1.0 - p3s3) * (1.0 - p3s4) - p4;
                        double p2s1 = pmap[make_pair(K, s[0].substr(2, 3))];
                        double p2s2 = pmap[make_pair(K, s[1].substr(2, 3))];
                        double p2s3 = pmap[make_pair(K, s[2].substr(2, 3))];
                        double p2s4 = pmap[make_pair(K, s[3].substr(2, 3))];
                        double p2 = 1.0 - (1.0 - p2s1) * (1.0 - p2s2) * (1.0 - p2s3) * (1.0 - p2s4) - p4 - p3;
                        s[0][3] = s[1][3] = s[2][3] = s[3][3] = '?';
                        r4 += p4 / K;
                        r3 += p3 / K;
                        r2 += p2 / K;
                    }
                    sol += r4 * s4 + r3 * s3 + r2 * s2;
                } else {
                    double p4s1 = pmap[make_pair(K, s[0])];
                    double p4s2 = pmap[make_pair(K, s[1])];
                    double p4s3 = pmap[make_pair(K, s[2])];
                    double p4s4 = pmap[make_pair(K, s[3])];
                    double p4 = 1.0 - (1.0 - p4s1) * (1.0 - p4s2) * (1.0 - p4s3) * (1.0 - p4s4);
                    double p3s1 = pmap[make_pair(K, s[0].substr(1, 5))];
                    double p3s2 = pmap[make_pair(K, s[1].substr(1, 5))];
                    double p3s3 = pmap[make_pair(K, s[2].substr(1, 5))];
                    double p3s4 = pmap[make_pair(K, s[3].substr(1, 5))];
                    double p3 = 1.0 - (1.0 - p3s1) * (1.0 - p3s2) * (1.0 - p3s3) * (1.0 - p3s4) - p4;
                    double p2s1 = pmap[make_pair(K, s[0].substr(2, 3))];
                    double p2s2 = pmap[make_pair(K, s[1].substr(2, 3))];
                    double p2s3 = pmap[make_pair(K, s[2].substr(2, 3))];
                    double p2s4 = pmap[make_pair(K, s[3].substr(2, 3))];
                    double p2 = 1.0 - (1.0 - p2s1) * (1.0 - p2s2) * (1.0 - p2s3) * (1.0 - p2s4) - p4 - p3;
                    sol += p4 * s4 + p3 * s3 + p2 * s2;
                }
            }
        }
        printf("Case #%d: %.7lf\n", cn, sol);
    }
}