You find yourself on an unusual crossroad with a weird traffic light. That traffic light has three possible colors: red (r), yellow (y), green (g). It is known that the traffic light repeats its colors every $n$ seconds and at the $i$-th second the color $s_i$ is on.

That way, the order of the colors is described by a string. For example, if $s=$"rggry", then the traffic light works as the following: red-green-green-red-yellow-red-green-green-red-yellow- ... and so on.

More formally, you are given a string $s_1, s_2, \ldots, s_n$ of length $n$. At the first second the color $s_1$ is on, at the second — $s_2$, ..., at the $n$-th second the color $s_n$ is on, at the $n + 1$-st second the color $s_1$ is on and so on.

You need to cross the road and that can only be done when the green color is on.

You know which color is on the traffic light at the moment, but you don't know the current moment of time. You need to find the minimum amount of time in which you are guaranteed to cross the road.

You can assume that you cross the road immediately.

For example, with $s=$"rggry" and the current color r there are two options: either the green color will be on after $1$ second, or after $3$. That way, the answer is equal to $3$ — that is the number of seconds that we are guaranteed to cross the road, if the current color is r.


-----Input-----

The first line contains a single integer $t$ $(1 \leq t \leq 10^4$) — the number of test cases.

Then the description of the test cases follows.

The first line of each test case contains an integer $n$ and a symbol $c$ ($1 \leq n \leq 2 \cdot 10^5$, $c$ is one of allowed traffic light colors r, y or g)— the length of the string $s$ and the current color of the traffic light.

The second line of each test case contains a string $s$ of the length $n$, consisting of the letters r, y and g.

It is guaranteed that the symbol g is in the string $s$ and the symbol $c$ is in the string $s$.

It is guaranteed, that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case output the minimal number of second in which you are guaranteed to cross the road.


-----Examples-----

Input
6
5 r
rggry
1 g
g
3 r
rrg
5 y
yrrgy
7 r
rgrgyrg
9 y
rrrgyyygy
Output
3
0
2
4
1
4


-----Note-----

The first test case is explained in the statement.

In the second test case the green color is on so you can cross the road immediately.

In the third test case, if the red color was on at the second second, then we would wait for the green color for one second, and if the red light was on at the first second, then we would wait for the green light for two seconds.

In the fourth test case the longest we would wait for the green color is if we wait for it starting from the fifth second.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Amortized analysis

Implementation


Solutions:
a = int(input())
ans = []
for i in range(a):
	(q, w) = input().split()
	z = input().split('g')
	z.append(z[-1] + z[0])
	if w == 'g':
		ans.append(0)
	else:
		maqs = 0
		for k in z:
			if w in k:
				maqs = max(len(k) - k.find(w), maqs)
		ans.append(maqs)
for t in ans:
	print(t)


t = int(input())
out = []
for i in range(t):
	(n, c) = input().split()
	n = int(n)
	arr = input() * 2
	start = False
	startsec = None
	wait = 0
	if c == 'g':
		out.append(0)
	else:
		for k in range(n):
			if arr[k] == c and start == False:
				start = True
				startsec = k
			elif arr[k] == 'g' and start == True:
				start = False
				wait = max(wait, k - startsec)
		if start == True:
			wait = max(arr.find('g', n) - startsec, wait)
		out.append(wait)
for i in out:
	print(i)


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a, c):
	a = a + a
	a = list(a)
	if c == 'g':
		print(0)
		return
	best = 0
	cur = 0
	s = False
	for i in a:
		if i == c:
			s = True
		if s:
			if i != 'g':
				cur += 1
			else:
				best = max(cur, best)
				cur = 0
				s = False
	print(best)
t = ni()
for case in range(t):
	(n, c) = INP().split()
	a = INP()
	solve(n, a, c)


for _ in range(int(input())):
	(n, c) = input().split()
	n = int(n)
	s = input()
	if c == 'g':
		print(0)
		continue
	first_green = p = None
	b = True
	ans = 0
	for i in range(n):
		if s[i] == c:
			b = True
			if p is None:
				p = i
		elif s[i] == 'g':
			b = False
			if first_green is None:
				first_green = i
			if p is not None:
				ans = max(ans, i - p)
				p = None
	if b:
		ans = max(ans, n - p + first_green)
	print(ans)


def solve(s, symbol):
	if s == 'g' and 'g' in s:
		return 0
	symbol_pos = -1
	g_pos = -1
	distance = 0
	for (i, e) in enumerate(s):
		if e == symbol:
			if symbol_pos == -1:
				symbol_pos = i
		elif e == 'g':
			if symbol_pos > -1:
				distance = max(distance, i - symbol_pos)
				symbol_pos = -1
			if g_pos == -1:
				g_pos = i
	if g_pos > -1 and symbol_pos > -1:
		distance = max(distance, g_pos + (len(s) - symbol_pos))
	return distance
t = int(input())
for _ in range(t):
	(n, symbol) = input().split()
	s = input()
	print(solve(s, symbol))


class Solution:

	def solve(n: str, state: str, light: str):
		n = int(n)
		if state == 'g':
			return '0'
		start = -1
		dis = 0
		gr_first = -1
		for i in range(n):
			if light[i] == state and start == -1:
				start = i
			if light[i] == 'g' and start != -1:
				dis = max(dis, i - start)
				start = -1
			if gr_first == -1 and light[i] == 'g':
				gr_first = i
		if start != -1:
			dis = max(dis, n - start + gr_first)
		return dis

	def trafficLight():
		for i in range(int(input())):
			(n, state) = list(input().split())
			light = input()
			print(Solution.solve(n, state, light))
Solution.trafficLight()


def opr():
	s = input().split()
	n = int(s[0])
	q = s[1]
	s = input()
	if q == 'g':
		print(0)
		return
	ans = -1
	pos = -1
	state = False
	firstg = -1
	for i in range(n):
		if firstg == -1 and s[i] == 'g':
			firstg = i
		if s[i] == q and (not state):
			pos = i
			state = True
		if s[i] == 'g' and state:
			ans = max(ans, i - pos)
			state = False
	if state:
		ans = max(ans, n + firstg - pos)
	print(ans)
T = int(input())
while T > 0:
	T -= 1
	opr()


from collections import defaultdict
from sys import stdin, stdout
import string

def solution(N, s, A):
	if s == 'g':
		return '0'
	min_sign_idx = N + 1
	min_green_idx = -1
	distance = -1
	for (idx, a) in enumerate(A):
		if a == s:
			min_sign_idx = min(min_sign_idx, idx)
		elif a == 'g' and min_green_idx == -1:
			min_green_idx = idx
		if a == 'g' and min_sign_idx != -1:
			distance = max(distance, idx - min_sign_idx)
			min_sign_idx = N + 1
	if min_sign_idx != N + 1:
		distance = max(distance, N - min_sign_idx + min_green_idx)
	return distance
test_cases = int(stdin.readline())
for it in range(test_cases):
	(N, s) = (x for x in stdin.readline().split())
	A = stdin.readline()
	print(solution(int(N), s, A))


t = int(input())
l = []
for i in range(t):
	x1 = list(input().split())
	n = int(x1[0])
	c = str(x1[1])
	b = list(input())
	k = []
	count = 0
	x = False
	for i in b:
		if x == True:
			count += 1
		if c == 'g':
			k.append(0)
		elif i == c:
			x = True
		elif i == 'g':
			x = False
			if count == 1:
				k.append(count)
			else:
				k.append(count)
			count = 0
	if x == True:
		k.append(count + b.index('g') + 1)
	l.append(max(k))
	k.clear()
for i in l:
	print(i)


for _ in range(int(input())):
	(__, c) = input().split()
	s = input()
	prevs = -1
	ans = 0
	for i in range(len(s)):
		if prevs == -1 and s[i] == c:
			prevs = i
		if s[i] == 'g' and prevs != -1:
			ans = max(ans, i - prevs)
			prevs = -1
	if prevs != -1:
		ans = max(ans, len(s) - prevs + s.find('g'))
	print(ans)


for i in ' ' * int(input()):
	(n, c) = input().split()
	n = int(n)
	s = input() * 2
	index = 0
	ozhid = False
	dist = -1
	max_d = -1
	if c == 'g':
		print(0)
	else:
		for i in s:
			if i == c and (not ozhid):
				dist = 1
				ozhid = True
			elif i == 'g' and ozhid:
				max_d = max(max_d, dist)
				ozhid = False
				dist = -1
			elif ozhid:
				dist += 1
		print(max_d)


import sys
readline = sys.stdin.readline
T = int(readline())
for i in range(T):
	(N, S) = readline().split()
	N = int(N)
	A = list(readline().rstrip()) * 2 + ['g']
	if S == 'g':
		print(0)
	else:
		cnt = -1
		MAX = 0
		for a in A:
			if a == 'g' and cnt >= 0:
				MAX = max(MAX, cnt + 1)
				cnt = -1
			elif cnt >= 0:
				cnt += 1
			elif a == S:
				cnt = 0
		print(MAX)


for _ in range(int(input())):
	(n, cur_c) = input().split()
	n = int(n)
	s = input() * 2
	ans = 0
	cur_idx = -1
	if cur_c == 'g':
		print(0)
		continue
	for (i, c) in enumerate(s):
		if c == cur_c and cur_idx == -1:
			cur_idx = i
		elif c == 'g' and cur_idx != -1:
			ans = max(ans, i - cur_idx)
			cur_idx = -1
	print(ans)


def timer(str, que, lenth):
	count = 0
	counter = 0
	i = 0
	k = 0
	if que == 'g':
		return 0
	while i < lenth:
		if str[i] == que:
			j = i + 1
			counter += 1
			while j < lenth and str[j] != 'g':
				counter += 1
				j += 1
			if j == len(str):
				j = 0
				k = 1
				while str[j] != 'g' and j < lenth:
					counter += 1
					j += 1
			i = j + 1
			if counter > count:
				count = counter
			counter = 0
			if k == 1:
				break
		else:
			i += 1
	return count
t = int(input())
for i in range(t):
	inputer = input().split()
	n = int(inputer[0])
	query = inputer[1]
	stringer = str(input())
	print(timer(stringer, query, n))


t = int(input())
for _ in range(t):
	(n, c) = input().split()
	n = int(n)
	s = str(input())
	if c == 'g':
		print(0)
	else:
		indl = -1
		indc = -1
		ind = 0
		time = 0
		for i in range(n - 1, -1, -1):
			if s[i] == 'g':
				if indl == -1:
					indl = i
				indc = i
			elif s[i] == c:
				if indl != -1:
					if indc - i > time:
						time = indc - i
				else:
					ind = i
		if n - ind + indc > time and ind != 0:
			time = n - ind + indc
		print(time)


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def inl():
	return list(input().split())

def insr():
	s = input()
	return list(s)

def invr():
	return map(int, input().split())
a = inp()
for _ in range(a):
	dict = {}
	z = inl()
	z = z[1]
	k = insr()
	(first, z1) = (-1, -1)
	c = 0
	if z == 'g':
		print(0)
		continue
	for i in range(len(k)):
		if k[i] == 'g' and first == -1:
			first = i
		if k[i] == z and z1 == -1:
			z1 = i
		if k[i] == 'g' and z1 != -1:
			c = max(c, i - z1)
			z1 = -1
	if z1 != -1:
		c = max(c, len(k) - z1 + first)
	print(c)


def solve():
	(N, s) = input().split()
	S = input()
	if s == 'g':
		return 0
	answer = 0
	high = len(S)
	for (indx, c) in enumerate(S):
		if c == 'g':
			first = indx
			break
	answer = 0
	flagChar = False
	lastSeenG = 0
	for i in range(high):
		if S[i] == s and (not flagChar):
			prev = i
			flagChar = True
		if flagChar and S[i] == 'g':
			answer = max(answer, i - prev)
			flagChar = False
		if S[i] == 'g':
			lastSeenG = i
	lastSeenS = 0
	for i in range(high - 1, lastSeenG, -1):
		if S[i] == s:
			lastSeenS = i
	if lastSeenS < lastSeenG:
		return answer
	return max(answer, high + first - lastSeenS)

def solution():
	t = int(input())
	for _ in range(t):
		temp = solve()
		print(temp)
solution()


t = int(input())
while t:
	(n, q) = input().split()
	s = input()
	n = int(n)
	if q == 'g':
		print(0)
		t -= 1
		continue
	x = s.index('g')
	p1 = 0
	p2 = 0
	ma = 0
	f = 1
	for i in range(n):
		if s[i] == 'g' and f == 0:
			p2 = i
			f = 1
			ma = max(ma, abs(p1 - p2))
		if s[i] == q and f == 1:
			p1 = i
			f = 0
	if f == 0:
		ma = max(ma, abs(n - p1 + x))
	print(ma)
	t -= 1


t = int(input())
for _ in range(t):
	(n, c) = input().strip().split()
	n = int(n)
	s = input()
	counter = 0
	g_count = 0
	result = 0
	first = False
	start = False
	if c == 'g':
		result = 0
	else:
		for x in s:
			if not first:
				g_count += 1
				if x == 'g':
					first = True
			if not start:
				if x == c:
					counter = 0
					start = True
			else:
				counter += 1
				if x == 'g':
					result = max(counter, result)
					start = False
		if start:
			counter += g_count
			result = max(counter, result)
	print(result)


for _ in range(int(input())):
	(n, c) = input().split()
	string = input()
	if c == 'g':
		print(0)
		continue
	spl = string.split('g')
	if string[0] != 'g' and string[-1] != 'g':
		spl[-1] += spl[0]
		spl = spl[1:]
	maximum = 0
	for l in spl[0:]:
		if len(l) > maximum:
			if c in l:
				m = len(l) - l.find(c)
				if m > maximum:
					maximum = m
	print(maximum)


def helper(s, k):
	first = -1
	ans = float('-inf')
	(l, r) = (-1, -1)
	if k == 'g':
		return 0
	for i in range(len(s)):
		if s[i] == 'g' and r <= l:
			r = i
			if first == -1:
				first = i
		if s[i] == k and l <= r:
			l = i
		if r != -1 and l != -1:
			ans = max(ans, r - l)
	if r <= l:
		return max(ans, len(s) - l + first)
	else:
		return ans
for i in range(int(input())):
	inp = input().split(' ')
	k = inp[1]
	s = input()
	print(helper(s, k))


t = int(input())
for _ in range(t):
	(n, color) = input().split()
	n = int(n)
	m = input()
	max_x = 0
	p = m.index('g') + 1
	if color == 'g':
		print(0)
	else:
		i = 0
		while i < n:
			x = 0
			if m[i] == color:
				for j in range(i + 1, n):
					x += 1
					if m[j] == 'g':
						break
				else:
					x += p
				i += x
				if max_x < x:
					max_x = x
			i += 1
		print(max_x)


p = int(input())
for _ in range(p):
	(_, col) = input().split(' ')
	seq = input()
	seq += seq
	if col == 'g':
		print(0)
	else:
		m = 0
		do = False
		cnt = 0
		for c in seq:
			if c == 'g' and do:
				do = False
				if cnt > m:
					m = cnt
				cnt = 0
			elif do:
				cnt += 1
			elif c == col:
				do = True
				cnt += 1
		print(m)


def main():
	n = int(input())
	for k in range(n):
		(length, ch) = input().rstrip().split()
		length = int(length)
		seq = input().rstrip()
		counts = []
		i = 0
		if ch == 'g':
			print(0)
		else:
			while i < length:
				if seq[i] == ch:
					j = i
					count = 0
					while j < length:
						if j == length - 1 and seq[j] != 'g':
							j = -1
							i = length
						elif seq[j] == 'g':
							counts.append(count)
							break
						j = j + 1
						count += 1
					i = i + count
				i = i + 1
			print(max(counts))
main()


def func(letter, sequence):
	if letter == 'g':
		return 0
	maxs = 0
	count = -1
	letter_found = False
	calculate_first_count = False
	firstc = 0
	flag = True
	gfound = False
	firstg = False
	flag2 = True
	g = ''
	for (index, value) in enumerate(sequence):
		if value == 'g':
			gx = index
			gfound = True
			first_g = True
			if first_g and flag2:
				g = index
				flag2 = False
			count += 1
			if calculate_first_count:
				firstc = count
				calculate_first_count = False
				flag = False
				x = 0
			maxs = max(count, maxs)
			count = -1
			letter_found = False
			continue
		if value == letter:
			letter_found = True
		if letter_found:
			count += 1
		if letter_found and flag:
			calculate_first_count = True
			if not gfound:
				x = index
			else:
				x = g
	end = 0
	if sequence[-1] != 'g' and seq.find(l, gx) != -1:
		end = int(length) - seq.find(l, gx) + seq.find('g')
	maxs = max(end, maxs)
	return maxs
tests = int(input())
for i in range(tests):
	inp = input().split()
	length = inp[0]
	l = inp[1]
	seq = input()
	print(func(l, seq))


def func(letter, sequence):
	if letter == 'g':
		return 0
	maxs = 0
	count = -1
	letter_found = False
	flag = True
	currentl = 0
	currentg = 0
	nextpos = True
	for (index, value) in enumerate(sequence):
		if value == 'g':
			nextpos = True
			currentg = index
			first_g = True
			if first_g and flag:
				g_1 = index
				flag = False
			count += 1
			maxs = max(count, maxs)
			count = -1
			letter_found = False
			continue
		if value == letter:
			letter_found = True
			if nextpos:
				currentl = index
				nextpos = False
		if letter_found:
			count += 1
	end = 0
	if sequence[-1] != 'g' and currentl > currentg:
		end = int(length) - currentl + g_1
	maxs = max(end, maxs)
	return maxs
tests = int(input())
for i in range(tests):
	inp = input().split()
	length = inp[0]
	l = inp[1]
	seq = input()
	print(func(l, seq))


def get_next_index(s, size, index, color):
	while index < size:
		if s[index] != color:
			index += 1
		else:
			return index
	return None

def solution():
	test_cases = int(input())
	for _ in range(test_cases):
		first_line = input().split()
		(size, current_color) = (int(first_line[0]), first_line[1])
		s = input()
		if current_color == 'g':
			print(0)
			continue
		seconds = 0
		index = get_next_index(s, size, 0, current_color)
		curr_seconds = 0
		flag = False
		while index != None and index < size:
			if s[index] != 'g':
				if index == size - 1:
					flag = True
				index = (index + 1) % size
				curr_seconds += 1
			else:
				seconds = max(seconds, curr_seconds)
				curr_seconds = 0
				next_index = get_next_index(s, size, index, current_color)
				if flag or not next_index:
					break
				else:
					index = next_index
		print(seconds)
solution()


t = int(input())
for t1 in range(t):
	(a, c) = input().split()
	n = int(a)
	s = input()
	max = 0
	if c == 'g':
		print(0)
	else:
		max = 0
		i = 0
		while i < n:
			while i < n and s[i] != c:
				i += 1
			j = i
			while j < n and s[j] != 'g':
				j += 1
				if j == n:
					k = 0
					while s[k] != 'g':
						k += 1
					if k - i + n > max:
						max = k - i + n
			if i < n and j < n and (j - i > max):
				max = j - i
			i = j
		print(max)


for i in range(int(input())):
	(n, zv) = input().split()
	n = int(n)
	z = input()
	d = {'r': 0, 'y': 0, 'g': 0}
	if z[-1] == 'g':
		g = 0
		for i in range(n - 1, -1, -1):
			if z[i] == 'g':
				g = 0
			else:
				g += 1
				if d[z[i]] < g:
					d[z[i]] = g
	else:
		j = z.find('g')
		g = 0
		for i in range(j - 1, -1, -1):
			if z[i] == 'g':
				g = 0
			else:
				g += 1
				if d[z[i]] < g:
					d[z[i]] = g
		for i in range(n - 1, j, -1):
			if z[i] == 'g':
				g = 0
			else:
				g += 1
				if d[z[i]] < g:
					d[z[i]] = g
	print(d[zv])


for _ in range(int(input())):
	(len1, b) = input().split()
	len1 = int(len1)
	list1 = list(input())
	max1 = 0
	if b == 'g':
		print(0)
		continue
	flag = False
	for i in range(len1):
		if not flag and list1[i] == b:
			flag = True
			start = i
		elif list1[i] == 'g' and flag:
			max1 = max(max1, i - start)
			flag = False
	if flag:
		for i in range(len1, 2 * len1):
			j = i % len1
			if list1[j] == 'g':
				max1 = max(i - start, max1)
				break
	print(max1)


n = int(input())
for sjfa in range(n):
	infor = input().split()
	length = infor[0]
	current = infor[1]
	list = input().split('g')
	if current == 'g':
		print(0)
		continue
	list[-1] += list[0]
	largest = 0
	for x in range(len(list)):
		if list[x] != '' and current in list[x]:
			inde = list[x].index(current)
			new = list[x][inde:]
			list[x] = new
			if len(new) > largest:
				largest = len(new)
	print(largest)


def main():
	n_tests = int(input())
	for _ in range(n_tests):
		(n, l) = list(input().split(' '))
		n = int(n)
		arr = input()
		if l == 'g':
			print(0)
			continue
		max_val = 0
		start_pos = None
		for i in range(2 * n):
			pos = i % n
			if arr[pos] == l and start_pos is None:
				start_pos = i
				continue
			if arr[pos] == 'g' and start_pos is not None:
				diff = i - start_pos
				if diff > max_val:
					max_val = diff
				start_pos = None
		print(max_val)
main()


t = int(input())
for _ in range(t):
	(n, c) = input().split()
	n = int(n)
	a = input()
	if c == 'g':
		print(0)
	else:
		most_left_g = None
		mlf_found = False
		cur_c = None
		this_c_found = None
		w_case = -1
		for i in range(n):
			if a[i] == 'g':
				if not mlf_found:
					mlf_found = True
					most_left_g = i
				if cur_c is not None:
					w_case = max(w_case, i - cur_c)
					this_c_found = True
					cur_c = None
			elif a[i] == c:
				if this_c_found or this_c_found is None:
					cur_c = i
					this_c_found = False
		if not this_c_found:
			w_case = max(w_case, n - cur_c + most_left_g)
		print(w_case)


tc = int(input())
for t in range(tc):
	(n, c) = [x for x in input().split()]
	n = int(n)
	s = input()
	if c == 'g':
		print(0)
		continue
	s = s[:] + s[:s.find('g') + 1]
	d = 0
	md = 0
	for i in s:
		if i == 'g':
			md = max(md, d)
			d = 0
		elif i == c and d == 0:
			d = 1
			continue
		if d != 0:
			d += 1
	print(md)


testcases = int(input())

def find_max_dist(current, pattern):
	path = pattern + pattern
	max_dist = -1
	looking_for_start = True
	for i in range(len(path)):
		c = path[i]
		if c == current and looking_for_start:
			start = i
			looking_for_start = False
		if c == 'g' and (not looking_for_start):
			dist = i - start
			if dist > max_dist:
				max_dist = dist
			looking_for_start = True
	return max_dist
for testcase in range(testcases):
	(repeats, current) = input().split()
	repeats = int(repeats)
	pattern = input()
	if current == 'g':
		print(0)
		continue
	print(find_max_dist(current, pattern))


def helper(s, k):
	left = -1
	right = -1
	front = -1
	ans = 0
	if k == 'g':
		return 0
	for i in range(len(s)):
		if s[i] == 'g' and front == -1:
			front = i
			right = i
		elif s[i] == k and (right > left or right + left == -2):
			left = i
		elif s[i] == 'g' and (right < left or right + left == -2):
			right = i
		if left != -1 and right != -1:
			ans = max(ans, right - left)
	if right < left:
		return max(ans, front + (len(s) - left))
	return ans
for i in range(int(input())):
	arr = list(input().split())
	k = arr[1]
	print(helper(input(), k))


for _ in range(int(input())):
	(n, colour) = input().split()
	s = input()
	if colour == 'g':
		print(0)
		continue
	s += s
	ans = 0
	l = last = s.index(colour)
	for i in range(l + 1, 2 * int(n)):
		if last != -1:
			if s[i] == 'g':
				ans = max(ans, i - last)
				last = -1
		elif s[i] == colour:
			last = i
	print(ans)


t = int(input())
for i in range(t):
	(n, c) = input().split()
	s = input()
	t = 0
	if c != 'g':
		n = int(n)
		length = len(s)
		i = 0
		to_continue = True
		while i < length and to_continue:
			ct = 1
			if s[i] == c:
				j = i + 1
				if j == length:
					i = length
					j = 0
					to_continue = False
				while s[j] != 'g':
					ct += 1
					j = j + 1
					if j == length:
						i = length
						j = 0
						to_continue = False
				if ct > t:
					t = ct
				if to_continue == True:
					i = j + 1
			else:
				i += 1
	print(t)


t = int(input())
for i in range(t):
	(n, c) = input().split()
	n = int(n)
	s = input()
	s += s

	def fun(s):
		if c == 'g':
			return 0
		stack = []
		answer = 0
		for i in range(2 * n - 1):
			if len(stack) == 1 and s[i] == 'g':
				answer = max(answer, i - stack.pop())
			if not stack and s[i] == c:
				stack.append(i)
		return answer
	print(fun(s))


for test in range(int(input())):
	(n, c) = input().split()
	n = int(n)
	lks = input()
	prev = -1
	ans = 0
	for (pos, char) in enumerate(lks):
		if char == c and prev == -1:
			prev = pos
		elif char == 'g' and prev != -1:
			ans = max(ans, pos - prev)
			prev = -1
	if prev != -1:
		ans = max(ans, n - prev + lks.find('g'))
	if c == 'g':
		print(0)
	else:
		print(ans)


for _ in range(int(input())):
	nt = input().split()
	lights = input()
	n = int(nt[0])
	if nt[1] == 'g':
		print(0)
		continue
	mint = lights.index('g')
	stack = []
	ans = 0
	for i in range(n):
		if lights[i] == nt[1]:
			stack.append(i)
		elif lights[i] == 'g':
			if stack:
				ans = max(ans, i - stack[0])
				stack = []
	while stack:
		ans = max(ans, n - stack.pop() + mint)
	print(ans)


t = int(input())
for i in range(t):
	(n, c) = input().split()
	n = int(n)
	s = input()
	if c == 'g':
		print(0)
		continue
	a = s.count(c)
	ng = s.count('g')
	if a < ng:
		left = 0
		max = 0
		rememberw = 0
		for j in range(a):
			q = s.find(c, left, n)
			w = s.find('g', q, n)
			if w == rememberw:
				left = q + 1
				continue
			if w != -1:
				if w - q > max:
					max = w - q
			elif n - q + s.find('g') > max:
				max = n - q + s.find('g')
			left = q + 1
			rememberw = w
		print(max)
	else:
		left = 0
		max = 0
		for j in range(ng):
			w = s.find('g', left, n)
			q = s.find(c, left, w)
			if q != -1:
				if w - q > max:
					max = w - q
			left = w + 1
		q = s.find(c, left, n)
		if q != -1:
			if n - q + s.find('g') > max:
				max = n - q + s.find('g')
		print(max)


t = int(input())
while t > 0:
	t -= 1
	(x, c) = input().split()
	s = input()
	(l, r) = (-1, -1)
	firstG = -1
	result = 0
	if c == 'g':
		print('0')
		continue
	for i in range(len(s)):
		if s[i] == c and l == -1:
			l = i
		if s[i] == 'g':
			if l >= 0:
				r = i
			if firstG == -1:
				firstG = i
		if l < r and l >= 0 and (r >= 0):
			result = max(result, r - l)
			l = -1
			r = -1
	if l >= 0 and r == -1:
		result = max(result, len(s) - l + firstG)
	print(result)


for _ in range(int(input())):
	(n, k) = map(str, input().split())
	n = int(n)
	s = str(input())
	if k == 'g':
		print(0)
	else:
		s = s + s
		ans = 0
		i = 0
		while i < n:
			if s[i] == k:
				for j in range(i + 1, 2 * n):
					if s[j] == 'g':
						ans = max(ans, j - i)
						i = j + 1
						break
			else:
				i += 1
		print(ans)


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n, c) = inp_str_arr()
	s = inp_str()
	n = int(n)
	ind = 0
	if c == 'g':
		print(0)
		return
	for i in range(n):
		if s[i] == 'g':
			ind = i
			break
	last_ind = -1
	i = int((ind + 1) % n)
	ans = 0
	flag = 0
	while flag == 0 or i != ind + 1:
		flag = 1
		i = int(i % n)
		if s[i] == c and last_ind == -1:
			last_ind = i
		if s[i] == 'g' and last_ind != -1:
			diff = i - last_ind
			if diff < 0:
				diff += n
			ans = max(ans, diff)
			last_ind = -1
		i += 1
	print(ans)
(tt,) = inp_arr()
for t in range(tt):
	solve()


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(s, n, c):
	if c == 'g':
		return 0
	s *= 2
	ans = 0
	pre = s.index(c)
	for i in range(pre, 2 * n):
		if s[i] == 'g' and pre != -1:
			ans = max(ans, i - pre)
			pre = -1
		elif s[i] == c and pre == -1:
			pre = i
	return ans
t = int(input())
for _ in range(t):
	arr = input().split()
	n = int(arr[0])
	c = arr[1]
	s = input()
	print(solve(s, n, c))


import math
from collections import defaultdict
for i in range(int(input())):
	(n, c) = map(str, input().split())
	n = int(n)
	s = input()
	ind = s.find('g')
	exs = s + s[:ind + 1]
	ans = 0
	count = 0
	if c == 'g':
		print(0)
		continue
	flag = True
	for j in exs:
		if j == c:
			if flag == True:
				count = 0
				flag = False
		if j == 'g' and flag == False:
			ans = max(ans, count)
			flag = True
			count = 0
		count += 1
	print(ans)


t = int(input())
while t != 0:
	(n, c) = [x for x in input().split()]
	n = int(n)
	s = input()
	prev = 'g'
	if c == 'g':
		print(0)
	else:
		maxm = -10000000000.0
		for i in range(n):
			if s[i] == c and prev != c:
				c_ind = i
				prev = c
			elif s[i] == 'g' and prev == c:
				g_ind = i
				maxm = max(maxm, g_ind - c_ind)
				prev = 'g'
		if prev == c:
			g_ind = s.index('g')
			maxm = max(maxm, n - c_ind + g_ind)
		print(maxm)
	t -= 1


T = int(input())
while T:
	(n, q) = input().split()
	s = input()
	n = int(n)
	if q == 'g':
		print(0)
		T -= 1
		continue
	seen = 0
	first = -1
	maxsofar = 0
	d = []
	for i in range(n):
		if s[i] == q:
			d.append(i)
		if s[i] == 'g':
			if d != [] and i - d[0] > maxsofar:
				maxsofar = i - d[0]
				d.pop(0)
			if seen == 0:
				first = i
				seen = 1
			d = []
	if d != []:
		if n - (d[0] - first) > maxsofar:
			maxsofar = n - (d[0] - first)
	print(maxsofar)
	T -= 1


from collections import defaultdict
t = int(input())

def solve():
	(n, c) = input().split()
	n = int(n)
	s = input()
	if c == 'g':
		print(0)
		return
	first_occurence = -1
	for i in range(n):
		if s[i] == 'g':
			first_occurence = i
			break
	mx = 0
	if c == 'y':
		i = 0
		while i < n:
			if s[i] == c:
				k = i
				i += 1
				while i < n and s[i] != 'g':
					i += 1
				if i == n:
					mx = max(mx, first_occurence + n - k)
				else:
					mx = max(mx, i - k)
			i += 1
		print(mx)
	elif c == 'r':
		i = 0
		while i < n:
			if s[i] == c:
				k = i
				i += 1
				while i < n and s[i] != 'g':
					i += 1
				if i == n:
					mx = max(mx, first_occurence + n - k)
				else:
					mx = max(mx, i - k)
			i += 1
		print(mx)
while t:
	solve()
	t -= 1


t = int(input())
while t:
	(n, x) = input().split()
	n = int(n)
	s = input()
	if x == 'g':
		print(0)
	else:
		flag = False
		arr = []
		for i in range(n):
			if not flag and s[i] == x:
				flag = True
				idx = i
			elif flag and s[i] == 'g':
				arr.append(i - idx)
				flag = False
		for i in range(n):
			if s[i] == 'g':
				idx = i
				break
		for i in range(n):
			if s[n - i - 1] == x:
				i2 = n - i - 1
			elif s[n - i - 1] == 'g':
				break
		if flag:
			arr.append(abs(n - (i2 - idx)))
		print(max(arr))
	t -= 1


t = int(input())
for h in range(t):
	(n, c) = input().split()
	s = input()
	n = int(n)
	flag = 1
	r = 1
	m = 0
	for i in range(n):
		if s[i] == c:
			if r:
				r = 0
				start = i
		if s[i] == 'g':
			if flag:
				flag = 0
				store = i
			if r == 0:
				r = 1
				m = max(m, i - start)
	if r == 0:
		m = max(m, n - start + store)
	print(m)


for _i in range(int(input())):
	(n, c) = map(str, input().split())
	n = int(n)
	s = input()
	if c == 'g':
		print(0)
		continue
	i = 0
	m = 0
	while i < n:
		if s[i] == c:
			j = i
			x = 0
			while s[j] != 'g':
				j += 1
				if j == n:
					j = 0
				x += 1
			i += x
			m = max(x, m)
		else:
			i += 1
	print(m)


t = int(input())

def solve(n, start, string):
	green = [0] * n
	lst = []
	(initial, distance) = (0, 0)
	if start == 'g':
		return 0
	for i in range(n - 1, -1, -1):
		if string[i] == 'g':
			initial = i
			break
	for i in range(initial - 1, -1, -1):
		distance += 1
		if string[i] == 'g':
			green[i] = 0
			distance = 0
		else:
			if string[i] == start:
				lst.append(distance)
			green[i] = distance
	for i in range(initial + 1, n):
		green[i] = n - i + green[0]
		if string[i] == start:
			lst.append(green[i])
	return max(lst)
for i in range(t):
	(n, init) = input().split()
	n = int(n)
	string = list(input())
	print(solve(n, init, string))


import sys
import threading
from functools import lru_cache
from bisect import bisect_left
from collections import defaultdict, deque

def main():
	t = int(input())
	for _ in range(t):
		(n, c) = [i for i in input().split()]
		n = int(n)
		s = input()
		ans = 0
		stack = []
		for index in range(n):
			if s[index] == 'g' and stack:
				cur = stack.pop()
				ans = max(ans, index - cur)
			elif s[index] == c:
				if not stack:
					stack.append(index)
		if stack:
			cur = stack.pop()
			index = s.index('g')
			ans = max(ans, index + 1 + (n - 1 - cur))
		if c == 'g':
			ans = 0
		print(ans)
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


T = int(input())
for i in range(T):
	(N, color) = input().split()
	N = int(N)
	str = input()
	if color == 'g':
		print(0)
		continue
	counter = 0
	answer_list = []
	for j in range(N):
		if counter == 0:
			if str[j] == color:
				counter += 1
		elif str[j] == 'g':
			answer_list.append(counter)
			counter = 0
		else:
			counter += 1
	for j in range(N):
		if counter == 0:
			if str[j] == color:
				counter += 1
		elif str[j] == 'g':
			answer_list.append(counter)
			counter = 0
		else:
			counter += 1
	print(max(answer_list))


def solve(a, s):
	m = {}
	for i in range(len(a)):
		if a[i] in m.keys():
			if m[a[i]] != s[i]:
				return 'NO'
		else:
			m[a[i]] = s[i]
	return 'YES'
t = int(input())
while t > 0:
	t -= 1
	[n, q] = [j for j in input().split()]
	n = int(n)
	s = input()
	ans = -189
	s = s + s
	last = -1
	if q == 'g':
		print(0)
		continue
	for i in range(2 * n):
		if s[i] == q and last == -1:
			last = i
		if s[i] == 'g' and last != -1:
			ans = max(i - last, ans) if ans != -189 else i - last
			last = -1
	print(ans)


from sys import stdin, stdout
import sys
sys.setrecursionlimit(100000)

def fxn(n, x, s):
	max = 0
	k = 0
	p = True
	i = 0
	if x == 'g':
		return max
	while i < n:
		if s[i] == x:
			for k in range(i, 2 * n):
				if s[k % n] == 'g' and k - i > max:
					max = k - i
					i = k
					break
				elif s[k % n] == 'g':
					break
		i += 1
	return max

def main():
	t = int(input())
	while t != 0:
		arr0 = [x for x in input().split()]
		n = int(arr0[0])
		x = arr0[1]
		s = input()
		print(fxn(n, x, s))
		t -= 1
main()


t = int(input())
for _ in range(t):
	(n, c) = input().split()
	n = int(n)
	s = input()
	i = 0
	mx = 0
	while i < n:
		if s[i] == c:
			j = 0
			while s[(i + j) % n] != 'g':
				j += 1
			mx = max(mx, j)
			i += j + 1
		else:
			i += 1
	print(mx)


t = int(input())
for i in range(t):
	(n, start) = input().split(' ')
	s = input()
	if start == 'g':
		print(0)
		continue
	possibilities = []
	n = int(n)
	first = n
	last = -1
	for j in range(len(s)):
		if s[j] == start:
			if last == -1:
				last = j
		elif s[j] == 'g':
			if j < first:
				first = j
			if last != -1:
				possibilities.append(j - last)
				last = -1
	if last != -1:
		possibilities.append(n - last + first)
	print(max(possibilities))


for i in range(int(input())):
	c = input().split()[1][0]
	s = input() * 2
	i1 = -1
	rango = -1
	for (indice, j) in enumerate(s):
		if j == 'g':
			if i1 != -1:
				if rango < indice - i1:
					rango = indice - i1
				i1 = -1
		elif j == c:
			if i1 == -1:
				i1 = indice
	if c == 'g':
		rango = 0
	print(rango)


for _ in range(int(input())):
	(n, c) = input().split()
	s = input()
	add = s.find('g')
	n = int(n) + add
	s = s + s[:add]
	dist = []
	index = 0
	if c == 'g':
		print(0)
		continue
	while index < n:
		while index < n and s[index] != c:
			index += 1
		start = index
		while index < n and s[index] != 'g':
			index += 1
		end = index
		dist.append(end - start)
	print(max(dist))


def solve():
	a = input().split()
	n = int(a[0])
	c = a[1]
	s = input()
	if c == 'g':
		print(0)
	else:
		i = 0
		l = []
		while i < n:
			if s[i] == 'g':
				a = i - 1
				sec = 0
				while s[a] != 'g':
					if a < 0:
						a = n - 1
					sec += 1
					if s[a] == c:
						l.append(sec)
					a -= 1
			i += 1
		print(max(l))
t = int(input())
while t > 0:
	solve()
	t -= 1


t = int(input())
for i in range(t):
	d = input().split(' ')
	n = int(d[0])
	c = d[1]
	s = input()
	dic = []
	init = -1
	q = []
	ans = 0
	for i in range(n):
		if s[i] == c:
			q.append(i)
		if s[i] == 'g':
			if init == -1:
				init = i
			if q != []:
				a = q[0]
				ans = max(ans, i - a)
			q.clear()
	if q != []:
		a = q[0]
		ans = max(ans, n - a + init)
	print(ans)


from heapq import heappush, heappop, heapify
from collections import Counter

def getIntegerInputs():
	return map(int, input().split())

def getListInput():
	return list(map(int, input().split()))

def inbound(r, c, n, m):
	return 0 <= r < n and 0 <= c < m

def solve():
	for _ in range(int(input())):
		(n, s) = map(str, input().split())
		n = int(n)
		w = input()
		dic = {}
		flag = False
		r = 0
		ans = 0
		for i in range(n - 1, -1, -1):
			dic[w[i]] = i
			if w[i] == s and 'g' not in dic:
				flag = True
				r = n - i
			elif w[i] == s:
				ans = max(ans, dic['g'] - dic[s])
		if flag:
			ans = max(ans, dic['g'] + r)
		print(ans)
solve()


def func():
	(x, r) = input().split()
	x = int(x)
	s = input()
	w = [0] * x
	for i in range(x):
		if s[i] == 'g':
			ind = i
			break
	if s[x - 1] != 'g':
		w[x - 1] = ind + 1
	for i in range(x - 2, -1, -1):
		if s[i] != 'g':
			w[i] = 1 + w[i + 1]
	maxi = 0
	for i in range(x):
		if s[i] == r and w[i] > maxi:
			maxi = w[i]
	return maxi
t = int(input())
for i in range(t):
	ans = func()
	print(ans)


def solution(s, n, c):
	if c == 'g':
		return 0
	dist = []
	start = s.index(c)
	s = s + s[:s.index('g') + 1]
	d = 0
	target = True
	for i in range(start, len(s)):
		if s[i] == 'g' and target == True:
			dist.append(d)
			target = False
		elif s[i] == c and target == False:
			d = 0
			target = True
		d += 1
	return max(dist)
result = []
t = int(input())
for i in range(t):
	(n, c) = [x for x in input().split(' ')]
	n = int(n)
	s = input()
	result.append(solution(s, n, c))
for res in result:
	print(res)


n = int(input())
for _ in range(n):
	(_, my_light) = input().split()
	lights = input() * 2
	time = -1
	cur_d = 0
	in_progress = False
	if my_light == 'g':
		print(0)
		continue
	for l in lights:
		cur_d += 1
		if l == 'g' and in_progress:
			time = max(cur_d, time)
			in_progress = False
		if l == my_light and (not in_progress):
			cur_d = 0
			in_progress = True
	print(time)


for i in range(int(input())):
	(n, c) = input().split()
	n = int(n)
	s = input()
	if c == 'g':
		print(0)
	else:
		ans = 0
		cp = 0
		c_i = -1
		for i in range(n):
			if cp == 0 and s[i] == c:
				c_i = i
				cp = 1
			if s[i] == 'g' and c_i != -1:
				ans = max(ans, i - c_i)
				cp = 0
				c_i = -1
		if c_i != -1:
			for i in range(n):
				if s[i] == 'g':
					ans = max(ans, n - c_i + i)
					break
		print(ans)


t = int(input())
while t > 0:
	(n, ch) = input().split(' ')
	n = int(n)
	x = input()
	ans = 0
	idx = 0
	idxg = 0
	for i in range(n):
		if x[i] == 'g':
			idxg = i
			break
	if ch == 'g':
		print(0)
	else:
		i = 0
		idx = 0
		while i < n:
			if x[i] == ch:
				while idx < n:
					if x[idx] == 'g':
						ans = max(ans, idx - i)
						break
					idx += 1
				if idx == n:
					ans = max(ans, n - i + idxg)
			idx += 1
			i = idx
		print(ans)
	t -= 1


for i in range(int(input())):
	(a, b) = input().split()
	x = input() * 2
	c = False
	v = m = 0
	for j in x:
		if j == b:
			c = True
		if j == 'g':
			c = False
			if v > m:
				m = v
			v = 0
		if c:
			v += 1
	print(m)


import sys
t = int(sys.stdin.readline())
res = []
for i in range(0, t):
	n_colorC = list(map(str, sys.stdin.readline().split()))
	n_color = int(n_colorC[0])
	starting_color = n_colorC[1]
	string_input = sys.stdin.readline()
	colors = list(string_input)
	tmp_duration = 0
	mx = 0
	start_i = 0
	fragment_start = False
	for i in range(start_i, n_color):
		if colors[i] == starting_color and tmp_duration == 0:
			fragment_start = True
		if fragment_start:
			tmp_duration += 1
		if tmp_duration > 0 and colors[i] == 'g':
			mx = max(mx, tmp_duration - 1)
			tmp_duration = 0
			fragment_start = False
	if tmp_duration > 0 and fragment_start:
		for i in range(start_i, n_color):
			tmp_duration += 1
			if colors[i] == 'g':
				mx = max(mx, tmp_duration - 1)
				break
	res.append(mx)
for data in res:
	print(data)


t = int(input())
for i in range(t):
	[n, c] = input().split()
	s = input()
	s = 2 * s
	l = []
	max = 0
	i = 0
	while i < int(n):
		if s[i] == c:
			count = 0
			while s[i] != 'g':
				count += 1
				i += 1
			if count > max:
				max = count
		i += 1
	print(max)


def one():
	(n, c) = input().split()
	n = int(n)
	s = input()
	q = [None] * n
	i = s.index('g')
	for _ in range(n):
		if s[i] == 'g':
			q[i] = 0
		else:
			q[i] = q[i + 1] + 1
		i -= 1
	print(max((q[i] for i in range(n) if s[i] == c)))
t = int(input())
for i in range(t):
	one()


def ans(c, s):
	if c == 'g':
		return 0
	first = -1
	for i in range(len(s)):
		if s[i] == 'g':
			first = i
			break
	if first == -1:
		return -1
	start = -1
	max_val = 0
	for i in range(len(s)):
		if s[i] == c and start == -1:
			start = i
		if s[i] == 'g' and start != -1:
			max_val = max(max_val, i - start)
			start = -1
	if start != -1:
		max_val = max(max_val, len(s) - start + first)
	return max_val
for T in range(int(input())):
	(n, c) = map(str, input().split())
	s = input()
	print(ans(c, s))


for _ in range(int(input())):
	(n, c) = input().split()
	n = int(n)
	s = input()
	if c == 'g':
		print(0)
	else:
		d0 = -1
		rep = 0
		currD = 0
		for i in range(n):
			if s[i] == 'g':
				if d0 == -1:
					d0 = i
				rep = max(rep, currD)
				currD = 0
			elif s[i] == c or currD != 0:
				currD += 1
		else:
			if currD != 0:
				rep = max(rep, currD + d0)
		print(rep)


t = int(input())
for i in range(t):
	nc = input().strip().split()
	n = int(nc[0])
	c = nc[1]
	s = input()
	if c == 'g':
		print(0)
		continue
	news = s + s[:-1]
	ans = 0
	curlen = 0
	addpa = False
	for i in news:
		if addpa:
			curlen += 1
		if curlen == 0 and i == c:
			addpa = True
		if i == 'g':
			ans = max(curlen, ans)
			curlen = 0
			addpa = False
	print(ans)


fl = 'input.txt'
import sys
import math
flh = sys.stdin
test_cases = int(flh.readline())
res = []
for case in range(test_cases):
	(n, c) = [x for x in flh.readline().strip().split()]
	n = int(n)
	a = flh.readline().strip().split()[0]
	max_count = -math.inf
	x = 0
	g = 0
	a = a + a
	while x < len(a):
		while x < len(a) and a[x] != c:
			x += 1
		g = x
		while g < len(a) and a[g] != 'g':
			g += 1
		max_count = max(max_count, g - x)
		x = g + 1
	print(max_count)


t = int(input())
for _ in range(t):
	(n, sym) = input().split()
	n = int(n)
	s = input()
	if sym == 'g':
		print(0)
	else:
		s += s
		i = 0
		ans = 0
		while i < 2 * n:
			while i < 2 * n and s[i] != sym:
				i += 1
			start = i
			i += 1
			while i < 2 * n and s[i] != 'g':
				i += 1
			end = i
			i += 1
			ans = max(ans, end - start)
		print(ans)


from re import I
import sys
for _ in range(int(input())):
	(n, c) = input().split()
	s = input()
	if c == 'g':
		print(0)
	else:
		s2 = s + s
		f = -1
		ans = 0
		for i in range(len(s2)):
			if f == -1 and s2[i] == c:
				f = i
			elif f != -1 and s2[i] == 'g':
				ans = max(ans, i - f)
				f = -1
		print(ans)


from re import I
for _ in range(int(input())):
	a = [i for i in input().split()]
	b = input()
	b += b
	i = 0
	n = int(a[0]) * 2
	cur = a[1]
	time = 0
	if a[0] == 1 or cur == 'g':
		print(0)
		continue
	while i < n // 2:
		if b[i] != cur:
			i += 1
		else:
			(j, co) = (i, 0)
			while b[j] != 'g' and j < n:
				j += 1
				co += 1
			time = max(time, co)
			i = j + 1
	print(time)


t = int(input(''))
for j in range(t):
	l = input('').split()
	n = int(l[0])
	c = l[1]
	s = input('')
	s = s * 2
	a = 0
	if c == 'g':
		print(0)
		continue
	p = -1
	for i in range(2 * n):
		if s[i] == c and p == -1:
			p = i
		elif s[i] == 'g' and p != -1:
			d = i - p
			p = -1
			a = max(a, d)
	print(a)


test = int(input())
for _ in range(test):
	(n, cur) = map(str, input().split())
	s = str(input())
	if cur == 'g':
		print(0)
		continue
	(first, counts, dist, count) = (float('inf'), 0, 0, False)
	for i in range(len(s)):
		if s[i] == 'g':
			first = min(first, i)
			counts = max(counts, dist)
			dist = 0
			count = False
		if s[i] == cur:
			count = True
		if count:
			dist += 1
	ans = counts
	if dist > 0:
		ans = max(ans, dist + first)
	print(ans)


import sys
import math
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import heapq
sys.setrecursionlimit(200000)
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def cust():
	s = input()
	return s[:len(s) - 1]

def solve():
	tmp = cust().split()
	n = int(tmp[0])
	c = tmp[1]
	s = insr()
	if c == 'g':
		print(0)
		return
	ans = 0
	for i in range(n):
		if s[i] == 'g':
			curr = (i - 1) % n
			pathSum = 1
			while curr != i and s[curr] != 'g':
				if s[curr] == c:
					ans = max(ans, pathSum)
				pathSum += 1
				curr = (curr - 1) % n
	print(ans)
t = inp()
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, c) = input().split()
	n = int(n)
	s = input()
	s += s
	s = list(s)
	if c == 'g':
		print(0)
		continue
	if c == 'r':
		while s[0] != 'r':
			s.pop(0)
		k = 0
		m = 0
		for i in range(len(s)):
			if s[i] == 'r':
				k += 1
			elif s[i] == 'y':
				if k != 0:
					k += 1
			else:
				if k > m:
					m = k
				k = 0
		print(m)
	else:
		while s[0] != 'y':
			s.pop(0)
		k = 0
		m = 0
		for i in range(len(s)):
			if s[i] == 'y':
				k += 1
			elif s[i] == 'r':
				if k != 0:
					k += 1
			else:
				if k > m:
					m = k
				k = 0
		print(m)


for _ in range(int(input())):
	(a, q) = map(str, input().split())
	n = int(a)
	s = input()
	s1 = s + s
	f = 0
	m = 0
	if q == 'g':
		print(0)
	else:
		for x in s1:
			if f == 0:
				if x == q:
					f = 1
					sc = 0
			elif x == 'g':
				m = max(m, sc + 1)
				f = 0
			else:
				sc += 1
		print(m)


import heapq

class solution:

	def solve(self):
		(n, c) = input().split(' ')
		n = int(n)
		s = input()
		dp = [-1 for _ in range(n)]
		curr = -1
		for i in range(n - 1, -1, -1):
			if s[i] != 'g' and curr == -1:
				dp[i] = curr
			elif s[i] != 'g':
				curr += 1
				dp[i] = curr
			else:
				curr = 0
				dp[i] = curr
		i = n - 1
		while dp[i] == -1:
			curr += 1
			dp[i] = curr
			i -= 1
		ans = 0
		for i in range(n):
			if s[i] == c:
				if dp[i] > ans:
					ans = dp[i]
		print(ans)
sol = solution()
t = int(input())
for _ in range(t):
	sol.solve()


t = int(input())

def toint(arr):
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	return arr
for _ in range(t):
	(n, st) = input().split()
	n = int(n)
	s = input()
	ans = 0
	idx = 0
	first = -1
	s = s + s
	for i in range(n):
		if s[i] == 'g':
			first = i
			break
	while idx < n:
		if s[idx] != st:
			idx += 1
		else:
			start = idx
			temp = idx
			while s[temp] != 'g':
				temp += 1
			ans = max(temp - start, ans)
			idx = temp + 1
	print(ans)


t = int(input())
for i in range(t):
	(n, c) = input().split()
	s = input()
	x = [i for (i, x) in enumerate(s) if x == c]
	newS = s + s[:s.index('g') + 1]
	maxi = 0
	for i in range(len(x)):
		newS = newS[newS.index(c):]
		if len(newS) == 0:
			break
		tempS = newS[newS.index(c):newS.index('g')]
		if len(tempS) > maxi:
			maxi = len(tempS)
		if newS.index('g') == len(newS) - 1:
			break
		newS = newS[newS.index('g'):]
		if c not in newS:
			break
	print(maxi)


t = int(input())
for i in range(t):
	(a, c) = input().strip().split()
	n = int(a)
	s = input()
	if c == 'g':
		print(0)
	else:
		max_time = -1
		i = 0
		while i < n:
			time = 1
			if s[i] == c:
				j = (i + 1) % n
				for k in range(n - 1):
					if s[j] == 'g':
						if time > max_time:
							max_time = time
						break
					time += 1
					j = (j + 1) % n
				if j > i:
					i = j + 1
				else:
					break
			else:
				i += 1
		print(max_time)


a = int(input())
for y in range(a):
	(l, b) = map(str, input().split())
	c = input()
	c = c + c
	s = 0
	h = -1
	if b == 'g':
		print(0)
	else:
		for y in range(2 * int(l)):
			if c[y] == b and h == -1:
				h = y
			elif c[y] == 'g':
				if h != -1:
					s = max(s, y - h)
					h = -1
		print(s)


t = int(input())
for tc in range(t):
	(n, c) = input().split()
	s = input()
	answer = -1
	first_green = -1
	last_green = -1
	last_c = -1
	prev_c = -1
	if c == 'g':
		print('0')
	else:
		for i in range(len(s)):
			if s[i] == c and prev_c == -1:
				prev_c = i
			if s[i] == 'g':
				last_green = i
				if prev_c != -1 and answer < i - prev_c:
					answer = i - prev_c
				prev_c = -1
			if s[i] == c:
				last_c = i
			if s[i] == 'g' and first_green == -1:
				first_green = i
		if prev_c == -1:
			prev_c = last_c
		if first_green != -1 and min(last_c, prev_c) > last_green:
			answer = max(answer, int(n) - min(last_c, prev_c) + first_green)
		print(answer)


def crossRoad(n, c, s):
	found = False
	prev = 0
	res = 0
	if c == 'g':
		return 0
	for i in range(2 * n):
		idx = i % n
		if found:
			if s[idx] == 'g':
				res = max(res, i - prev)
				prev = 0
				found = False
		elif c == s[idx]:
			prev = i
			found = True
	return res
T = int(input())
for i in range(T):
	(n, c) = [i for i in input().split()]
	n = int(n)
	s = input()
	res = crossRoad(n, c, s)
	print(res)


t = int(input())
for i in range(t):
	nc = input().split()
	n = int(nc[0])
	c = nc[1]
	s = input()
	if c == 'g':
		print(0)
		continue
	s = s + s
	s = [*s]
	stack = []
	ret = []
	fs = 0
	for i in range(len(s)):
		if s[i] == c:
			fs = i
			break
	stack.append(fs)
	for i in range(fs + 1, len(s)):
		if stack and s[i] == 'g':
			val = i - stack[0]
			stack.pop()
			ret.append(val)
		elif not stack and s[i] == c:
			stack.append(i)
	print(max(ret))


tc = int(input())
for TC in range(tc):
	(n, c) = input().split()
	n = int(n)
	s = input()
	l = []
	(fc, fg) = (None, None)
	ans = 0
	if c == 'g':
		print('0')
		continue
	for i in s:
		if i == c or i == 'g':
			l.append(i)
		else:
			l.append(' ')
	ind = 1
	for i in l:
		if fg == None and i == 'g':
			fg = ind
		if fc == None and i == c:
			fc = ind
		if i == 'g' and fc != None:
			ans = max(ans, ind - fc)
			fc = None
		ind += 1
	if fc != None:
		ans = max(ans, n - fc + fg)
	print(ans)


N = int(input())
for x in range(N):
	line1 = input()
	line1 = line1.split()
	n = int(line1[0])
	c = line1[1]
	s = input()
	s *= 2
	output = 0
	if c == 'g':
		print(output)
		continue
	s = s.split('g')
	for i in s:
		for j in range(len(i)):
			if i[j] == c:
				if len(i) - j > output:
					output = len(i) - j
				break
	print(output)


t = int(input())
for i in range(t):
	(n, c) = list(map(str, input().split(sep=' ')))
	s = input()
	s = 2 * s
	n = int(n)
	j = 0
	k = 0
	m = 0
	if c == 'g':
		print(0)
	else:
		while j < n:
			if s[j] == c:
				if s[k] == 'g':
					m = max(m, k - j)
					j = k + 1
				k = k + 1
			else:
				j = j + 1
				k = j
		print(m)