{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIt\u0027s a walking tour day in SIS.Winter, so $$$t$$$ groups of students are visiting Torzhok. Streets of Torzhok are so narrow that students have to go in a row one after another.\u003c/p\u003e\u003cp\u003eInitially, some students are angry. Let\u0027s describe a group of students by a string of capital letters \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eP\u003c/span\u003e\": \u003c/p\u003e\u003cul\u003e \u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\" corresponds to an angry student \u003c/li\u003e\u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eP\u003c/span\u003e\" corresponds to a patient student \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eSuch string describes the row from the last to the first student.\u003c/p\u003e\u003cp\u003eEvery minute every angry student throws a snowball at the next student. Formally, if an angry student corresponds to the character with index $$$i$$$ in the string describing a group then they will throw a snowball at the student that corresponds to the character with index $$$i+1$$$ (students are given from the last to the first student). If the target student was not angry yet, they become angry. Even if the first (the rightmost in the string) student is angry, they don\u0027t throw a snowball since there is no one in front of them.\u003c/p\u003e\u003ccenter\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/9c46118ee78530a6e98e4d7e28d2e40f?v\u003d1716040399\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/center\u003e\u003cp\u003eLet\u0027s look at the first example test. The row initially looks like this: \u003cspan class\u003d\"tex-font-style-tt\"\u003ePPAP\u003c/span\u003e. Then, after a minute the only single angry student will throw a snowball at the student in front of them, and they also become angry: \u003cspan class\u003d\"tex-font-style-tt\"\u003ePPAA\u003c/span\u003e. After that, no more students will become angry.\u003c/p\u003e\u003cp\u003eYour task is to help SIS.Winter teachers to determine the last moment a student becomes angry for every group.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$t$$$\u0026nbsp;— the number of groups of students ($$$1 \\le t \\le 100$$$). The following $$$2t$$$ lines contain descriptions of groups of students.\u003c/p\u003e\u003cp\u003eThe description of the group starts with an integer $$$k_i$$$ ($$$1 \\le k_i \\le 100$$$)\u0026nbsp;— the number of students in the group, followed by a string $$$s_i$$$, consisting of $$$k_i$$$ letters \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eP\u003c/span\u003e\", which describes the $$$i$$$-th group of students.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor every group output single integer\u0026nbsp;— the last moment a student becomes angry.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4\nPPAP\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n12\nAPPAPPPAPPPP\n3\nAAP\n3\nPPA\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test, after $$$1$$$ minute the state of students becomes \u003cspan class\u003d\"tex-font-style-tt\"\u003ePPAA\u003c/span\u003e. After that, no new angry students will appear.\u003c/p\u003e\u003cp\u003eIn the second tets, state of students in the first group is: \u003c/p\u003e\u003cul\u003e \u003cli\u003e after $$$1$$$ minute\u0026nbsp;— \u003cspan class\u003d\"tex-font-style-tt\"\u003eAAPAAPPAAPPP\u003c/span\u003e \u003c/li\u003e\u003cli\u003e after $$$2$$$ minutes\u0026nbsp;— \u003cspan class\u003d\"tex-font-style-tt\"\u003eAAAAAAPAAAPP\u003c/span\u003e \u003c/li\u003e\u003cli\u003e after $$$3$$$ minutes\u0026nbsp;— \u003cspan class\u003d\"tex-font-style-tt\"\u003eAAAAAAAAAAAP\u003c/span\u003e \u003c/li\u003e\u003cli\u003e after $$$4$$$ minutes all $$$12$$$ students are angry \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eIn the second group after $$$1$$$ minute, all students are angry.\u003c/p\u003e"}}]}