Traffic Light

题意翻译

给定一个循环字符串的一个最小循环节。 求循环字符串中一种字母的右边的第一个 $\texttt{g}$ 字符的距离最大值，这个字母可以为循环节中任意一个位置，只要符合字母种类要求即可。 如字母种类为 $\texttt{r}$ ，循环节为 $\texttt{rggry}$ ，则我们可以选择位于第 $4$ 个位置的 $\texttt{r}$ ,即可达到最大距离的要求: $3$ 。 $\texttt{translated by }$[acwing_gza](/user/301255)

题目描述

You find yourself on an unusual crossroad with a weird traffic light. That traffic light has three possible colors: red (r), yellow (y), green (g). It is known that the traffic light repeats its colors every $ n $ seconds and at the $ i $ -th second the color $ s_i $ is on. That way, the order of the colors is described by a string. For example, if $ s= $ "rggry", then the traffic light works as the following: red-green-green-red-yellow-red-green-green-red-yellow- ... and so on. More formally, you are given a string $ s_1, s_2, \ldots, s_n $ of length $ n $ . At the first second the color $ s_1 $ is on, at the second — $ s_2 $ , ..., at the $ n $ -th second the color $ s_n $ is on, at the $ n + 1 $ -st second the color $ s_1 $ is on and so on. You need to cross the road and that can only be done when the green color is on. You know which color is on the traffic light at the moment, but you don't know the current moment of time. You need to find the minimum amount of time in which you are guaranteed to cross the road. You can assume that you cross the road immediately. For example, with $ s= $ "rggry" and the current color r there are two options: either the green color will be on after $ 1 $ second, or after $ 3 $ . That way, the answer is equal to $ 3 $ — that is the number of seconds that we are guaranteed to cross the road, if the current color is r.

输入输出格式

输入格式

The first line contains a single integer $ t $ $ (1 \leq t \leq 10^4 $ ) — the number of test cases. Then the description of the test cases follows. The first line of each test case contains an integer $ n $ and a symbol $ c $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ , $ c $ is one of allowed traffic light colors r, y or g)— the length of the string $ s $ and the current color of the traffic light. The second line of each test case contains a string $ s $ of the length $ n $ , consisting of the letters r, y and g. It is guaranteed that the symbol g is in the string $ s $ and the symbol $ c $ is in the string $ s $ . It is guaranteed, that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case output the minimal number of second in which you are guaranteed to cross the road.

输入输出样例

输入样例 #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

说明

The first test case is explained in the statement. In the second test case the green color is on so you can cross the road immediately. In the third test case, if the red color was on at the second second, then we would wait for the green color for one second, and if the red light was on at the first second, then we would wait for the green light for two seconds. In the fourth test case the longest we would wait for the green color is if we wait for it starting from the fifth second.

**题目大意：**

有一个交通灯，它的颜色按照一个长度为 $ n $ 的循环字符串 $ s $ 来变化，字符串中只包含字符 'r'（红色）、'y'（黄色）和 'g'（绿色）。在任意时刻，你需要知道从当前颜色变为绿色所需的最少秒数。例如，如果循环字符串是 "rggry"，并且当前颜色是红色，那么有两种情况：绿色灯亮要么是在 1 秒后，要么是在 3 秒后。因此，如果当前颜色是红色，答案就是 3 秒，这是你一定能通过路口的秒数。

**输入输出数据格式：**

**输入格式：**
- 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。
- 每个测试用例有两行：
- 第一行包含两个元素，一个整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $）和一个字符 $ c $（'r'、'y' 或 'g'），分别表示循环字符串的长度和当前的交通灯颜色。
- 第二行包含一个长度为 $ n $ 的字符串 $ s $，由 'r'、'y' 和 'g' 组成。

**输出格式：**
- 对于每个测试用例，输出一行，包含一个整数，表示从当前颜色变为绿色的最少秒数。

**输入输出样例：**

**输入样例 #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
```

**说明：**
- 第一个测试用例在题目描述中已经解释。
- 在第二个测试用例中，绿灯已经亮起，所以你可以立即通过路口。
- 在第三个测试用例中，如果你在第二秒是红灯，那么你会等待一秒绿灯，如果你在第一秒是红灯，那么你会等待两秒绿灯。
- 在第四个测试用例中，等待绿灯最长时间的情况是从第五秒开始等待。**题目大意：** 有一个交通灯，它的颜色按照一个长度为 $ n $ 的循环字符串 $ s $ 来变化，字符串中只包含字符 'r'（红色）、'y'（黄色）和 'g'（绿色）。在任意时刻，你需要知道从当前颜色变为绿色所需的最少秒数。例如，如果循环字符串是 "rggry"，并且当前颜色是红色，那么有两种情况：绿色灯亮要么是在 1 秒后，要么是在 3 秒后。因此，如果当前颜色是红色，答案就是 3 秒，这是你一定能通过路口的秒数。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。 - 每个测试用例有两行： - 第一行包含两个元素，一个整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $）和一个字符 $ c $（'r'、'y' 或 'g'），分别表示循环字符串的长度和当前的交通灯颜色。 - 第二行包含一个长度为 $ n $ 的字符串 $ s $，由 'r'、'y' 和 'g' 组成。 **输出格式：** - 对于每个测试用例，输出一行，包含一个整数，表示从当前颜色变为绿色的最少秒数。 **输入输出样例：** **输入样例 #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 ``` **说明：** - 第一个测试用例在题目描述中已经解释。 - 在第二个测试用例中，绿灯已经亮起，所以你可以立即通过路口。 - 在第三个测试用例中，如果你在第二秒是红灯，那么你会等待一秒绿灯，如果你在第一秒是红灯，那么你会等待两秒绿灯。 - 在第四个测试用例中，等待绿灯最长时间的情况是从第五秒开始等待。