CF1744C Traffic Light

你发现自己站在一个奇怪的十字路口，那里有一个不同寻常的红绿灯。这个红绿灯有三种可能的颜色：红色（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 翻译