달과 우산

Cody-Jamal은 자신의 최신 추상 미술 작품을 만들고 있다. 이 벽화는 기우는 달과 접힌 우산이 한 줄로 늘어선 형태다. 그런데 욕심 많은 저작권 사냥꾼들이 기우는 달은 대문자 C처럼 보이고 접힌 우산은 J처럼 보인다며 CJ와 JC에 대한 저작권을 주장한다. 따라서 벽화에 CJ가 나타날 때마다 Cody-Jamal은 X를 지불해야 하고, JC가 나타날 때마다 Y를 지불해야 한다.

Cody-Jamal은 그들에게 자신의 예술이 훼손되도록 내버려 둘 생각이 없으므로, 이미 그려진 것은 바꾸지 않는다. 대신 아직 비어 있는 칸은 저작권 비용을 최소화하도록 전략적으로 채우기로 했다.

예를 들어 CJ?CC?가 현재 벽화의 상태이고, C는 기우는 달, J는 접힌 우산, ?는 아직 기우는 달이나 접힌 우산 중 하나로 채워야 하는 칸이라 하자. 이때 벽화를 CJCCCC, CJCCCJ, CJJCCC, CJJCCJ로 완성할 수 있다. 첫 번째와 세 번째는 저작권료로 X+Y를 내야 하고, 두 번째와 네 번째는 2⋅X+Y를 내야 한다.

비용 X, Y와 벽화의 현재 상태를 나타내는 문자열이 주어질 때, 이 비용을 최소화하도록 벽화를 완성하면 Cody-Jamal은 저작권료로 얼마를 내야 하는가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 두 정수 X와 Y, 그리고 벽화의 현재 상태를 나타내는 문자열 S가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 완성된 벽화에 대해 Cody-Jamal이 내야 하는 최소 저작권료다.

• 1 ≤ T ≤ 100.
• S의 각 문자는 C, J, ? 중 하나다.