311276: CF1959D. Traffic Light

D. Traffic Lighttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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

Output

3
0
2
4
1
4

Note

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.

题目大意：
你在一个不寻常的十字路口，有一个奇怪的交通灯。这个交通灯有三种可能的颜色：红色（r）、黄色（y）、绿色（g）。已知交通灯每n秒重复一次颜色，在第i秒时颜色为s_i。

这样，颜色的顺序由一个字符串描述。例如，如果s="rggry"，那么交通灯的工作方式是：红-绿-绿-红-黄-红-绿-绿-红-黄-...，如此循环。

更正式地说，你得到一个长度为n的字符串s_1, s_2, ..., s_n。在第1秒时颜色为s_1，在第2秒时为s_2，...，在第n秒时为s_n，在第n+1秒时为s_1，等等。

你需要穿过马路，而那只能在绿色亮起时完成。

你知道交通灯当前的 color，但不知道当前的时刻。你需要找到最小的保证过马路的时刻。

你可以假设你立即穿过马路。

例如，当s="rggry"且当前颜色为r时，有两个选择：绿色要么在1秒后亮起，要么在3秒后亮起。这样，答案是3——这是如果我们从红色开始等待，保证过马路的秒数。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
然后是每个测试用例的描述。
每个测试用例的第一行包含一个整数n和一个符号c（1≤n≤2×10^5，c是允许的交通灯颜色之一，即r、y或g）——字符串s的长度和交通灯的当前颜色。
每个测试用例的第二行包含一个长度为n的字符串s，由字母r、y和g组成。
保证字符串s中包含符号g，且符号c也在字符串s中。
保证所有测试用例的n之和不超过2×10^5。

输出：
对于每个测试用例输出保证过马路的秒数。题目大意： 你在一个不寻常的十字路口，有一个奇怪的交通灯。这个交通灯有三种可能的颜色：红色（r）、黄色（y）、绿色（g）。已知交通灯每n秒重复一次颜色，在第i秒时颜色为s_i。 这样，颜色的顺序由一个字符串描述。例如，如果s="rggry"，那么交通灯的工作方式是：红-绿-绿-红-黄-红-绿-绿-红-黄-...，如此循环。 更正式地说，你得到一个长度为n的字符串s_1, s_2, ..., s_n。在第1秒时颜色为s_1，在第2秒时为s_2，...，在第n秒时为s_n，在第n+1秒时为s_1，等等。 你需要穿过马路，而那只能在绿色亮起时完成。 你知道交通灯当前的 color，但不知道当前的时刻。你需要找到最小的保证过马路的时刻。 你可以假设你立即穿过马路。 例如，当s="rggry"且当前颜色为r时，有两个选择：绿色要么在1秒后亮起，要么在3秒后亮起。这样，答案是3——这是如果我们从红色开始等待，保证过马路的秒数。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 然后是每个测试用例的描述。 每个测试用例的第一行包含一个整数n和一个符号c（1≤n≤2×10^5，c是允许的交通灯颜色之一，即r、y或g）——字符串s的长度和交通灯的当前颜色。 每个测试用例的第二行包含一个长度为n的字符串s，由字母r、y和g组成。 保证字符串s中包含符号g，且符号c也在字符串s中。 保证所有测试用例的n之和不超过2×10^5。 输出： 对于每个测试用例输出保证过马路的秒数。