题目描述

你发现自己站在一个奇怪的十字路口，那里有一个不同寻常的红绿灯。这个红绿灯有三种可能的颜色：红色（r）、黄色（y）、绿色（g）。已知红绿灯每 $n$ 秒循环一次颜色，并且在第 $i$ 秒时，亮起的颜色为 $s_i$。

因此，颜色的顺序由一个字符串描述。例如，如果 $s=$ "rggry"，那么红绿灯的工作方式如下：红-绿-绿-红-黄-红-绿-绿-红-黄-……，如此循环往复。

更正式地说，给定一个长度为 $n$ 的字符串 $s_1, s_2, \ldots, s_n$。在第 $1$ 秒时，亮起的颜色是 $s_1$，在第 $2$ 秒时是 $s_2$，……，在第 $n$ 秒时是 $s_n$，在第 $n+1$ 秒时又回到 $s_1$，以此类推。

你需要过马路，并且只能在绿灯亮起时才能通过。

你知道当前红绿灯亮着的颜色，但你并不知道当前具体是第几秒。你需要求出，无论当前是哪一秒，你最多需要等待多少秒才能保证能过马路。

你可以假设你在绿灯亮起时可以立刻过马路。

例如，$s=$ "rggry"，当前颜色为 r，有两种可能：要么 1 秒后亮绿灯，要么 3 秒后亮绿灯。因此，答案是 $3$，也就是无论当前是哪一秒，最多 $3$ 秒内一定能过马路。

输入格式

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

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ 和一个字符 $c$（$1 \leq n \leq 2 \times 10^5$，$c$ 是 r、y 或 g 之一）——字符串 $s$ 的长度和当前红绿灯的颜色。

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

保证字符串 $s$ 中一定包含字符 g，且一定包含字符 $c$。

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

输出格式

对于每个测试用例，输出一个整数，表示你最多需要等待多少秒才能保证能过马路。

说明/提示

第一个测试用例的解释见题面。

第二个测试用例中，绿灯已经亮起，因此你可以立刻过马路。

第三个测试用例中，如果红灯在第二秒亮起，则需要等待 1 秒才能等到绿灯；如果红灯在第一秒亮起，则需要等待 2 秒才能等到绿灯。

第四个测试用例中，最长的等待时间是从第五秒开始等待绿灯。

由 ChatGPT 4.1 翻译

样例

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

3
0
2
4
1
4