C. Светофор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы попали на необычный перекресток со странным светофором. У этого светофора есть три возможных цвета: красный (r), желтый (y), зеленый (g). Известно, что светофор повторяет свои цвета каждые $$$n$$$ секунд и в $$$i$$$-ю секунду горит цвет $$$s_i$$$.

Таким образом, порядок цветов задаётся строкой. Например, если $$$s=$$$«rggry», то светофор горит так: красный-зеленый-зеленый-красный-желтый-красный-зеленый-зеленый-красный-желтый- ... и так далее.

Более формально, вам дана строка $$$s_1, s_2, \ldots, s_n$$$ длины $$$n$$$. В первую секунду горит цвет $$$s_1$$$, во вторую $$$s_2$$$, ..., в $$$n$$$-ю секунду горит цвет $$$s_n$$$, в $$$n + 1$$$-ю секунду горит цвет $$$s_1$$$ и так далее.

Вам нужно перейти дорогу, и это можно сделать только тогда, когда на светофоре горит зеленый цвет.

Вам известно, какой сейчас цвет на светофоре, но вы не знаете текущей момент времени. Вам нужно найти минимальное время, в течение которого вы точно (наверняка) сможете перейти дорогу.

Можно считать, что дорогу мы проходим моментально.

Например, в случае $$$s=$$$«rggry» и текущего света r возможны два варианта: либо зеленый свет наступит через через $$$1$$$ секунду, либо через $$$3$$$. Таким образом, ответ равен $$$3$$$ — именно через столько секунд мы гарантированно сможем перейти дорогу, если текущий цвет r.

Входные данные

В первой строке входных данных дано единственное целое число $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных содержится целое число $$$n$$$ и символ $$$c$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$c$$$ является одним из допустимых цветов светофора r, y или g)— длина строки $$$s$$$ и текущий цвет светофора.

Во второй строке каждого набора входных данных содержится строка $$$s$$$ длины $$$n$$$, состоящая из символов r, y и g.

Гарантируется, что символ g встречается в строке $$$s$$$ и что символ $$$c$$$ встречается в строке $$$s$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество секунд, в течение которого можно гарантировано перейти дорогу.

Пример
Входные данные
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
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных уже сейчас горит зеленый цвет, поэтому можно перейти дорогу сразу же.

В третьем наборе входных данных если изначально горел красный цвет на второй секунде, то ждать зеленого цвета пришлось бы одну секунду, а если бы горел красный цвет на первой секунде, то уже две.

В четвертом наборе входных данных дольше всего ждать зеленый цвет мы будем с пятой секунды.