该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

你出现在一个奇怪的十字路口，前面有一个奇葩的红绿灯。红绿灯具有红（r），黄（y），绿（g）三种颜色。这个红绿灯每过n秒就 会重复。比如s=“rggry”，那么这个红绿灯就会这样工作：红-绿-绿-红-黄-红-绿-绿-红-黄...... 给定n个字符s1，s2，s3，......，sn。第一秒s1开启，第二秒s2开启......第n+1秒s1开启。 现在已知当前红绿灯的颜色，但是你不知道是第几秒，问你确保能够通过红绿灯需要多少秒？（通过红绿灯是秒过） 例如 s="rggry",已知当前颜色是红色，这就有两个方案：

1、1秒钟之后变绿，

2、3秒钟之后变绿。

答案为3，因为这样才能确保你能够通过交通灯。

输入格式：

一个正整数t，表示t组数据（1<= t <= 10^4)

对于每组测试数据包含

第一行一个正整数n（字符串长度）和符号c（r，g，y的一种）表示当前交通灯颜色 (1<= n <= 2*10^5)

第二行一个长度为n的字符串s。

输出格式：

一个正整数表示能通过红绿灯的最小秒数。

样例：

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

3
0
2
4
1
4

提示

O(t*n^2) 可AC