神秘红绿灯

题目背景

有一处奇怪十字路口，乐柠兔和噜噜遇到了一盏“会循环变化”的交通灯。

交通灯只有三种颜色：

• r：红色
• y：黄色
• g：绿色

它会按照固定顺序循环亮灯。

题目描述

交通灯的工作顺序由一个长度为 $n$ 的字符串 $s = s_1s_2\dots s_n$ 给出：

• 第 $1$ 秒亮 $s_1$
• 第 $2$ 秒亮 $s_2$
• …
• 第 $n$ 秒亮 $s_n$
• 第 $n+1$ 秒又回到 $s_1$，之后不断重复

例如：若 $s=\text{"rggry"}$，则亮灯序列为：

r g g r y r g g r y ...

过马路规则

• 只有当灯为绿色 g 时，乐柠兔才能过马路
• 一旦出现 g，可以立刻通过（不额外耗时）
• 现在，乐柠兔只知道“当前看到的颜色是 $c$”，但不知道此刻对应的是周期中的第几秒

任务

对每个测试用例，求出一个最小的等待时间 $T$，使得：

无论当前处于周期中的哪个位置（只要当前颜色确实为 $c$），等待不超过 $T$ 秒，一定能遇到一次绿色灯并过马路。

输入格式

第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例组数。

每组测试用例：

• 第一行输入整数 $n$ 与字符 $c$（$1\le n\le 2\times 10^5$，$c\in{r,y,g}$），分别表示字符串长度与当前颜色。
• 第二行输入长度为 $n$ 的字符串 $s$，仅由 r、y、g 组成。

输出格式

对每组测试用例输出一行一个整数：

表示在最坏情况下，乐柠兔保证能过马路所需的最少等待秒数。

样例

样例输入

3
5 r
rggry
1 g
g
3 r
rrg

样例输出

3
0
2

样例说明

以 s="rggry" 且当前颜色为 r 为例：

当前为 r 可能对应字符串中的不同位置，距离下一次 g 的时间可能为 1 秒或 3 秒。为了“保证”一定等到 g，答案为最坏情况的 3。

数据范围与约定

• $1\le t\le 10^4$
• $1\le n\le 2\times 10^5$
• 保证 g 一定在字符串 $s$ 中出现
• 保证当前颜色 $c$ 一定在字符串 $s$ 中出现
• 所有测试用例的 $n$ 之和不超过 $2\times 10^5$