1744C - Traffic Light - CodeForces Solution

t = int(input())
for i in range(t):
    n, c = input().split()
    n = int(n)
    s = input()
    if c == "g":
        print(0)
    else:
        firstGreen = -1
        r = -1
        maxminc = 0
        for j in range(len(s)):
            if s[j] == 'g' and firstGreen == -1:
                firstGreen = j
            elif s[j] == c:
                if j < r:
                    maxminc = max(maxminc, r - j)
                elif r == len(s):
                    maxminc = max(maxminc, n - j + firstGreen)
                else:
                    for i in range(j + 1, len(s)):
                        if s[i] == 'g':
                            r = i
                            break
                    if r < j + 1:
                        r = len(s)
                        maxminc = max(maxminc, n - j + firstGreen)
                    else:
                        maxminc = max(maxminc, r - j)
        print(maxminc)