题目描述

排灯节是印度的光明节。为了庆祝这个节日，人们用彩灯装饰房屋并燃放爆竹。每个人都喜爱排灯节，Pari 也不例外。Pari 非常喜欢灯，并且拥有超限的能力，因此她购买了无数个红色和蓝色的灯泡。作为一名程序员，她也热爱模式，因此她通过无限重复一个给定的有限模式 $S$ 来排列她的灯泡。

例如，如果 $S$ 是 BBRB，那么 Pari 构建的无限序列将是 BBRBBBRBBBRB...。

蓝色是 Pari 最喜欢的颜色，因此她想知道在她构建的无限序列中，第 $I$ 个灯泡到第 $J$ 个灯泡（包含两端）之间有多少个蓝色灯泡（灯泡从 $1$ 开始连续编号）。在上面的序列中，编号如下：

B B R B B B R B B B  R  B...
1 2 3 4 5 6 7 8 9 10 11 12

例如，在第 $4$ 个到第 $8$ 个位置之间有 $4$ 个蓝色灯泡，而在第 $10$ 个到第 $12$ 个之间只有 $2$ 个。

由于序列可能非常长，她写了一个程序来为她计数。你能做到同样的事情吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行是一个字符串 $S$，表示初始的有限模式。每个测试用例的第二行是两个空格分隔的整数 $I$ 和 $J$，含义如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Pari 的无限序列中第 $I$ 个到第 $J$ 个灯泡（包含两端）之间蓝色灯泡的数量。

3
BBRB
4 8
BBRB
10 12
BR
1 1000000

Case #1: 4
Case #2: 2
Case #3: 500000

提示

样例 #1 和 #2 的解释如上所述。

在样例 #3 中，奇数索引的灯泡总是蓝色，偶数索引的灯泡总是红色，因此在位置 $1$ 到 $10^6$ 之间有五十万个蓝色灯泡。

限制条件

$1 \le T \le 100$。

$1 \le$ $S$ 的长度 $\le 100$。

$S$ 的每个字符都是大写字母 B 或 R。

小数据集（测试集 1 – 可见）

$1 \le I \le J \le 10^6$。

大数据集（测试集 2 – 隐藏）

$1 \le I \le J \le 10^{18}$。

翻译由 DeepSeek V4 Pro 完成