### 问题描述 小蓝和小桥走在一条路上，眼前出现了一个奇怪的十字路口，只有一盏交通信号灯，但是这个交通信号灯有三种颜色：红色（$\texttt{r}$）、黄色（$\texttt{y}$）和绿色（$\texttt{g}$）。交通信号灯的颜色会在每 $n$ 秒钟循环一次，第 $i$ 秒钟交通信号灯的颜色为 $s_i$。 具体来说，颜色的顺序由一个字符串描述。例如，如果 $s=$"$\texttt{rggry}$"，那么交通灯的工作方式如下：红绿绿红黄红绿绿红黄……如此往复。 更正式地说，给定一个长度为 $n$ 的字符串 $s=s_1,s_2,\dots,s_n$。在第一秒钟，交通信号灯的颜色为 $s_1$，在第二秒钟为 $s_2$，以此类推，直到第 $n$ 秒钟颜色为 $s_n$，然后又开始循环。 现在，小蓝和小桥需要穿过马路，只有在绿灯亮的时候才能安全通过。 他们知道交通信号灯现在的颜色，但是不知道现在的时间，因此他们需要计算出最短的时间，保证在这个时间内绿灯一定会亮，这样他们才能安全地通过。 假设他们可以立即穿过马路。 例如，对于 $s=$"$\texttt{rggry}$"，如果当前颜色为 $\texttt{r}$，有两个选项：绿色将在 $1$ 秒钟后点亮，或在 $3$ 秒钟后点亮。因此答案为 $3$，这是我们保证能通过马路的最短时间，如果当前颜色为 $\texttt{r}$。 ### 输入格式 第一行包含一个整数 $t$，表示测试数据组数。 对于每组数据，第一行包含两个整数 $n$ 和一个字符 $c$，表示字符串 $s$ 的长度和当前交通信号灯的颜色。 第二行包含一个长度为 $n$ 的字符串 $s$，表示交通信号灯颜色的顺序。 ### 输出格式 对于每组数据，输出一个整数，表示最短的时间，保证在这个时间内绿灯一定会亮，可以安全通过。 ### 样例输入 ```txt 6 5 r rggry 1 g g 3 r rrg 5 y yrrgy 7 r rgrgyrg 9 y rrrgyyygy ``` ### 样例输出 ```txt 3 0 2 4 1 4 ``` ### 样例说明 第一个测试用例在题目描述中已经解释过了。 第二个测试用例中，绿灯亮着，所以你可以立即穿过马路。 第三个测试用例中，如果第二秒红灯亮着，那么我们需要等待一秒钟绿灯，如果第一秒红灯亮着，那么我们需要等待两秒钟绿灯。 第四个测试用例中，我们等待绿灯的最长时间是从第五秒开始等待。 ### 评测数据规模 对于 $100$% 的评测数据，$1\leq t \leq 5,1 \leq n \leq 2 \cdot 10^5$。