← 返回题目列表

Codeforces · 1744/C

C. 交通灯

中文机器翻译题面 查看原题

你发现自己处于一个不寻常的十字路口,有一个奇怪的红绿灯。该交通灯有三种可能的颜色:红色 (r)、黄色 (y)、绿色 (g)。众所周知,交通灯每 $$$n$$$ 秒重复一次其颜色,并且在第 $$$i$$$ 秒,颜色 $$$s_i$$$ 亮起。

这样,颜色的顺序由字符串描述。例如,如果 $$$s=$$$"rggry",则交通灯的工作方式如下:红-绿-绿-红-黄-红-绿-绿-红-黄- ... 等等。

更正式地说,你会得到一个长度为 $$$n$$$ 的字符串 $$$s_1, s_2, \ldots, s_n$$$。在第一秒,颜色 $$$s_1$$$ 开启,在第二秒 — $$$s_2$$$,...,在第 $$$n$$$ 秒,颜色 $$$s_n$$$ 开启,在 $$$n + 1$$$ 秒,颜色 $$$s_1$$$ 开启,依此类推。

您需要过马路,并且只有在绿色亮起时才能进行。

您知道此时交通灯是什么颜色,但您不知道当前的时间。您需要找到保证过马路的最短时间。

您可以假设您立即过马路。

例如,对于 $$$s=$$$"rggry" 和当前颜色 r,有两个选项:绿色将在 $$$1$$$ 秒后打开,或在 $$$3$$$ 后打开。这样,答案就等于 $$$3$$$——如果当前颜色是 r,那就是我们保证过马路的秒数。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — 测试用例的数量。

然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ 和一个符号 $$$c$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$c$$$ 是允许的交通灯颜色 r、y 或 g 之一)——字符串 $$$s$$$ 的长度和交通灯的当前颜色。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由字母r、y和g组成。

保证符号 g 在字符串 $$$s$$$ 中,符号 $$$c$$$ 在字符串 $$$s$$$ 中。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,输出保证您过马路的最小秒数。

示例

输入 #1

6
5 r
rggry
1 g
g
3 r
rrg
5 y
yrrgy
7 r
rgrgyrg
9 y
rrrgyyygy

输出 #1

3
0
2
4
1
4

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,绿色亮起,因此您可以立即过马路。

在第三个测试用例中,如果第二秒红灯亮,那么我们将等待绿灯一秒,如果第一秒红灯亮,那么我们将等待绿灯两秒。

在第四个测试用例中,我们等待绿色的最长时间是从第五秒开始等待。