CF1744C.Traffic Light

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.

你来到了一个奇特的十字路口，那里有一盏奇怪的交通灯。该交通灯有三种可能的颜色：红色（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$ —— 即当当前颜色为 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$.

第一行包含一个整数 $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 组成。

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

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

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

对于每个测试用例，输出你保证能穿过马路所需的最短秒数。

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.

第一个测试用例已在题目描述中说明。

第二个测试用例中，绿色信号灯亮起，因此你可以立即过马路。

第三个测试用例中，若红灯在第 2 秒时亮起，则需等待绿灯 1 秒；若红灯在第 1 秒时亮起，则需等待绿灯 2 秒。

第四个测试用例中，等待绿灯的最长时间出现在从第 5 秒开始等待的情形。