google code jam("moons&umbrellas")

#include <bits/stdc++.h>
using namespace std;
#define DISPLAY_CASE cout << "Case #" << __caseNr__ << ": ";
///********************
const int NMAX = 1003;
char s[NMAX];
int dp[NMAX][2], n;//0-c, 1-j

void doQ(int __caseNr__) {
    int x, y, ans;
    cin >> x >> y >> (s + 1);
    dp[1][0] = dp[1][1] = 0;
    n = strlen(s + 1);
    for (int i = 2; i <= n; i++) {
        if (s[i - 1] == '?') {
            if (s[i] == '?') {
                dp[i][1] = min(dp[i - 1][0] + x, dp[i - 1][1]);
                dp[i][0] = min(dp[i - 1][1] + y, dp[i - 1][0]);
            } else if (s[i] == 'C') {
                dp[i][0] = min({dp[i - 1][0], dp[i - 1][1] + y});
                dp[i][1] = 1e9;
            } else if (s[i] == 'J') {
                dp[i][0] = 1e9;
                dp[i][1] = min({dp[i - 1][1], dp[i - 1][0] + x});
            }
        } else if (s[i - 1] == 'C') {
            if (s[i] == '?') {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][0] + x;
            } else if (s[i] == 'C') {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = 1e9;
            } else if (s[i] == 'J') {
                dp[i][0] = 1e9;
                dp[i][1] = dp[i - 1][0] + x;
            }
        } else if (s[i - 1] == 'J') {
            if (s[i] == '?') {
                dp[i][0] = dp[i - 1][1] + y;
                dp[i][1] = dp[i - 1][1];
            } else if (s[i] == 'C') {
                dp[i][0] = dp[i - 1][1] + y;
                dp[i][1] = 1e9;
            } else if (s[i] == 'J') {
                dp[i][0] = 1e9;
                dp[i][1] = dp[i - 1][1];
            }
        }
    }/*
    for (int i = 1; i <= n; i++) {
        cout << dp[i][0] << ' '<< dp[i][1] << endl;
    }//*/
    DISPLAY_CASE
    cout << min(dp[n][0], dp[n][1]) << "\n";
}

int main() {
    int q(1);
    cin >> q;
    for (int i = 1; i <= q; i++) {
        doQ(i);
    }
    return 0;
}