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 \cdot X + Y$。

给定费用 $X$ 和 $Y$ 以及代表壁画当前状态的字符串，如果 Cody-Jamal 以最小化成本的方式完成壁画，他需要支付多少版权费？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行。每行包含两个整数 $X$ 和 $Y$，以及一个字符串 $S$，分别代表两种费用和壁画的当前状态。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Cody-Jamal 完成壁画所需支付的最小版权费用。

数据范围

$1 \le T \le 100$。 字符串 $S$ 中的每个字符要么是 C，要么是 J，要么是 ?。

测试集 1（可见判决） $1 \le$ $S$ 的长度 $\le 10$。 $1 \le X \le 100$。 $1 \le Y \le 100$。

测试集 2（可见判决） $1 \le$ $S$ 的长度 $\le 1000$。 $1 \le X \le 100$。 $1 \le Y \le 100$。

额外加分！ 如果某些版权持有者可以为广告向 Cody-Jamal 付费而不是向他收费呢？Cody-Jamal 获得报酬用负数费用表示。

测试集 3（隐藏判决） $1 \le$ $S$ 的长度 $\le 1000$。 $-100 \le X \le 100$。 $-100 \le Y \le 100$。

样例

输入 1

4
2 3 CJ?CC?
4 2 CJCJ
1 3 C?J
2 5 ??J???

输出 1

Case #1: 5
Case #2: 10
Case #3: 1
Case #4: 0

说明 1

样例 1 是题目描述中解释的情况。最小成本为 $X + Y = 2 + 3 = 5$。

在样例 2 中，Cody-Jamal 的壁画已经完成，所以他没有选择。他的壁画中有两个 CJ 和一个 JC。

在样例 3 中，将 ? 替换为 C 或 J，会导致从第二个和第三个字符或第一个和第二个字符中产生一个 CJ。

在样例 4 中，Cody-Jamal 可以将壁画全部填为 J。由于其中不包含任何 CJ 或 JC，因此不需要支付版权费。

输入 2

1
2 -5 ??JJ??

输出 2

Case #1: -8

说明 2

在测试集 3 的样例 1 中，Cody-Jamal 可以将壁画最优地完成为 JCJJCC 或 JCJJJC。无论哪种方式，他的壁画中都有一个 CJ 和两个 JC。