// Arup Guha
// 3/27/2021
// Solution to 2021 Code Jam Qualifying Question B: Moons and Umbrellas
 
import java.util.*;

public class Solution {
	
	public static int[][] min;
	public static int[][] max;
	public static int x;
	public static int y;
	public static char[] s;
	public static int n;

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process all cases.
		for (int loop=1; loop<=nC; loop++) {
		
			// Get input.
			x = stdin.nextInt();
			y = stdin.nextInt();
			s = stdin.next().toCharArray();
			n = s.length;
			
			// Get forced characters.
			ArrayList<Character> str = new ArrayList<Character>();
			for (int i=0; i<s.length; i++)
				if (s[i] != '?')
					str.add(s[i]);
				
			// Get # of transitions.
			int numC = 0;
			for (int i=0; i<str.size()-1; i++)
				if (!str.get(i).equals(str.get(i+1)))
					numC++;
				
			// Both have cost. We minimize transitions...
			if (x >= 0 && y >= 0) {
				
				// Cost for almost all of the transitions bouncing back and forth.
				int res = (numC/2)*(x+y);
				
				// If it's odd, one transition occurs one more time. Add it.
				if (numC%2 == 1) {
					if (str.get(0) == 'C') res += x;
					else res += y;
				}
				
				// Ta da!
				System.out.println("Case #"+loop+": "+res);
				
			}
			
			// Easy case.
			else if (n == 1) System.out.println("Case #"+loop+": 0");
			
			// Here we deal with the more general case.
			else {
				
				// Here we store the minimum and maximum # of transitions depending on the starting and ending of the string.
				min = new int[2][2];
				max = new int[2][2];
				for (int i=0; i<4; i++) {
					min[i/2][i%2] = fillMin(i/2,i%2);
					max[i/2][i%2] = fillMax(i/2,i%2);
				}
				
				// High enough.
				int res = 1000000;
				
				
				// Just try all possibilities.	
				for (int i=0; i<2; i++) {
					for (int j=0; j<2; j++) {
						
						// This isn't possible, so continue.
						if (max[i][j] == -1) continue;
						
						// Get bounds on # of transitions. We can achieve everything in between.
						int high = max[i][j];
						int low = Math.max(min[i][j], high-1);
							
						// Just try all the options...
						for (int z=min[i][j]; z<=max[i][j]; z+=2) {
							if (i == 0) res = Math.min(res, ((z+1)/2)*x + (z/2)*y);
							else        res = Math.min(res, (z/2)*x + ((z+1)/2)*y);
						}
					}
				}
				
				// Ta da!
				System.out.println("Case #"+loop+": "+res);
			}
		}
	}
	
	// Returns the minimum # of transitions given that we start with character start (0=C,1=J) and end with character end.
	// Returns -1 otherwise.
	public static int fillMin(int start, int end) {
		
		// Contradictory information 
		if (s[0] == 'C' && start == 1) return -1;
		if (s[0] == 'J' && start == 0) return -1;
		if (s[n-1] == 'C' && end == 1) return -1;
		if (s[n-1] == 'J' && end == 0) return -1;
		
		// Fill in the string with the starting and ending.
		char[] tmp = new char[n];
		for (int i=0; i<n; i++) tmp[i] = s[i];
		tmp[0] = start == 0 ? 'C' : 'J';
		tmp[n-1] = end == 0 ? 'C' : 'J';
		
		// Run the same algorithm as before.
		int res = 0;
		for (int i=0; i<n-1; i++) {
			if (tmp[i+1] == '?') {
				tmp[i+1] = tmp[i] == 'C' ? 'C' : 'J';
			}
			if (tmp[i] != tmp[i+1])
				res++;
		}
		return res;
	}
	
	// Returns the maximum # of transitions given that we start with character start (0=C,1=J) and end with character end.
	// Returns -1 otherwise.	
	public static int fillMax(int start, int end) {
		
		// Contradictory information.
		if (s[0] == 'C' && start == 1) return -1;
		if (s[0] == 'J' && start == 0) return -1;
		if (s[n-1] == 'C' && end == 1) return -1;
		if (s[n-1] == 'J' && end == 0) return -1;
		
		// Fill in what we know.
		char[] tmp = new char[n];
		for (int i=0; i<n; i++) tmp[i] = s[i];
		tmp[0] = start == 0 ? 'C' : 'J';
		tmp[n-1] = end == 0 ? 'C' : 'J';
		
		// Always change, whenever possible.
		int res = 0;
		for (int i=0; i<n-1; i++) {
			if (tmp[i+1] == '?') {
				tmp[i+1] = tmp[i] == 'C' ? 'J' : 'C';
			}
			if (tmp[i] != tmp[i+1])
				res++;
		}
		return res;
	}	
}