A. Злые школьники
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ЛКШ.Зима день экскурсий, поэтому $$$t$$$ групп школьников отправились в Торжок. Тротуары в Торжке настолько узкие, что идти приходится в колонне по-одному.

Изначально некоторые из школьников злы. Для удобства будем описывать группу школьников строкой из заглавных латинских букв «A» и «P»:

  • «A» соответствует злому школьнику
  • «P» соответствует спокойному школьнику

Строка описывает школьников от последнего к первому, слева направо.

Каждую минуту каждый злой школьник кидает снежок в спину идущего непосредственно перед ним.

Формально, если злой школьник соответствует символу заданной строки с индексом $$$i$$$, то снежок он будет кидать в школьника, который соответствует символу с индексом $$$i+1$$$ (студенты в строке заданы от последнего к первому!). Если школьник, в которого попали снежком, еще не был зол, то он становится злым. Даже если первый (самый правый в строке) школьник является злым, он не бросает снежок, так как впереди него нет другого ученика.

Рассмотрим первый тестовый пример. В нем колонна изначально имеет такой вид: PPAP. Через минуту единственный злой школьник кинет снежок в школьника, идущего перед ним, и он тоже станет злым: PPAA. После этого, новых злых школьников появляться не будет.

Помогите преподавателям ЛКШ.Зима определить для каждой группы время, спустя которое в ней появится последний злой школьник.

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

В первой строке дано число $$$t$$$ ($$$1 \le t \le 100$$$) — количество групп школьников. Следующие $$$2t$$$ строк описывают группы школьников.

Описание группы начинается с целого числа $$$k_i$$$ ($$$1 \le k_i \le 100$$$) — количество школьников в группе, затем дана строка $$$s_i$$$, состоящая из $$$k_i$$$ символов «A» и «P», описывающая $$$i$$$-ю группу школьников.

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

Для каждой группы выведите в отдельной строке одно целое число — количество минут, через которое в этой группе появится последний злой школьник.

Примеры
Входные данные
1
4
PPAP
Выходные данные
1
Входные данные
3
12
APPAPPPAPPPP
3
AAP
3
PPA
Выходные данные
4
1
0
Примечание

В первом примере через $$$1$$$ минуту состояния школьников станут такими: PPAA после этого новых злых школьников не появится.

Во втором примере состояния школьников в первой группе по минутам будут выглядеть так:

  • через $$$1$$$ минуту — AAPAAPPAAPPP
  • через $$$2$$$ минуты — AAAAAAPAAAPP
  • через $$$3$$$ минуты — AAAAAAAAAAAP
  • через $$$4$$$ минуты злыми станут все $$$12$$$ школьников, поэтому новых злых школьников не появится.

Во второй группе второго примера через $$$1$$$ минуту все школьники станут злыми.