你发现自己处于一个不寻常的十字路口,有一个奇怪的红绿灯。该交通灯有三种可能的颜色:红色 (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
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,绿色亮起,因此您可以立即过马路。
在第三个测试用例中,如果第二秒红灯亮,那么我们将等待绿灯一秒,如果第一秒红灯亮,那么我们将等待绿灯两秒。
在第四个测试用例中,我们等待绿色的最长时间是从第五秒开始等待。