嘉航站在一个神奇的路口，这里的红绿灯也有三种颜色：红（r），黄（y），绿（g）；红绿灯每过 n 秒重复一次颜色，第 i 秒的颜色为 s[i]。例如，对于字符串 rygy，该红绿灯的工作方式为：红-黄-绿-黄-红-黄-绿-黄....以此类推。

更正式地说，对于一个长度为 n 的字符串 s[1],…,s[n]。在第一秒，灯的颜色为 s[1] ，在第二秒，颜色为 s[2]，在第 n 秒时，颜色为 s[n]，在第 n+1 秒时，颜色 s[1] 亮起，以此类推。

众所周知，只有绿灯亮起时，嘉航才能过马路。嘉航知道现在红绿灯的颜色 c ，但他不知道现在是第几秒，请你帮助嘉航找出保证能让他通过马路的最小等待时间。

例如，对于 s="rggry" ,当前颜色为红色(r)，那么绿灯将在 1 秒后或 3 秒后亮起。这样的话，答案就等于3，

第一行为一个整数 t（1<=t<=1e4），代表测试数据的数量。

对于每组测试数据，第一行为一个整数 n（1<=n<=2e5）与一个字符 c，分别代表字符串的长度与当前灯的颜色；

第二行为一个长度为 n 的字符串 s ，由字母 r 、y、g 组成，代表红绿灯的变化规律，保证 c 和字母 g 在 s中出现。

所有样例的 n 之和不超过 2e5。

第一组测试数据在题面中已给出解释；

在第二组测试数据中，绿灯是亮着的，所以嘉航可以立即过马路。
在第三组测试数据中，如果红灯在第二秒亮起，那么嘉航需要等待绿灯一秒，如果红灯在第一秒亮起，那么嘉航将等待绿灯两秒。