It's 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.

Initially, some students are angry. Let's describe a group of students by a string of capital letters "A" and "P":   "A" corresponds to an angry student  "P" corresponds to a patient student 

Such string describes the row from the last to the first student.

Every 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't throw a snowball since there is no one in front of them.

[Image]

Let's look at the first example test. The row initially looks like this: PPAP. 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: PPAA. After that, no more students will become angry.

Your task is to help SIS.Winter teachers to determine the last moment a student becomes angry for every group.


-----Input-----

The first line contains a single integer $t$ — the number of groups of students ($1 \le t \le 100$). The following $2t$ lines contain descriptions of groups of students.

The description of the group starts with an integer $k_i$ ($1 \le k_i \le 100$) — the number of students in the group, followed by a string $s_i$, consisting of $k_i$ letters "A" and "P", which describes the $i$-th group of students.


-----Output-----

For every group output single integer — the last moment a student becomes angry.


-----Examples-----
Input
1
4
PPAP

Output
1

Input
3
12
APPAPPPAPPPP
3
AAP
3
PPA

Output
4
1
0



-----Note-----

In the first test, after $1$ minute the state of students becomes PPAA. After that, no new angry students will appear.

In the second tets, state of students in the first group is:   after $1$ minute — AAPAAPPAAPPP  after $2$ minutes — AAAAAAPAAAPP  after $3$ minutes — AAAAAAAAAAAP  after $4$ minutes all $12$ students are angry 

In the second group after $1$ minute, all students are angry.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    data = input()
    count = 0
    while "AP" in data:
        data = data.replace("AP", "AA")
        count += 1
    print(count)


for _ in range(int(input())):
    n = int(input())
    s = input()
    res, prev = 0, -1
    for i, e in enumerate(s):
        if e == 'A':
            prev = i
        elif prev != -1:
            res = max(res, i - prev)
    print(res)


for i in range(int(input())):
    n = int(input())
    s = input()
    ans = -1e9
    cur = 0
    fl = False
    for j in range(n):
        if s[j] == 'A':
            fl = True
            ans = max(ans, cur)
            cur = 0
        elif fl == True:
            cur += 1
    print(max(cur, ans))

for _ in range(int(input())):
	n=int(input())
	s=input()
	curr=None
	ans=0
	for i in s:
		if i=="A":
			curr=0
		elif curr!=None:
			curr+=1
			ans=max(ans,curr)
	print(ans)

import sys

for _ in range(int(input())):
    k = int(input())
    a = input()
    res = 0
    cur = k - 1
    for i in range(k - 1, -1, -1):
        if a[i] == 'A':
            res = max(res, cur - i)
            cur = -1
        else:
            cur = max(cur, i)
    print(res)


def solve(s):
	last = -1
	c = 0
	m = 0
	for x in range(len(s)):
		if(s[x] == 'A'):
			last = x
			c = 0
		elif(last != -1):
			c += 1
			m = max(c, m)
	return m

n = int(input())
for x in range(n):
	k = int(input())
	s = input()
	print(solve(s))

for i in range(int(input())):
    k = int(input())
    BIG = input()
    max_ = 0
    calcer = 0
    f = 0
    for j in range(k):
        if BIG[j] == 'A':
            f = 1
            max_ = max(calcer, max_)
            calcer = 0
        if BIG[j] == 'P' and f:
            calcer += 1
    max_ = max(max_, calcer)
    print(max_)

Q = int(input())
for _ in range(Q):
    n = int(input())
    s = input()
    while s != '' and s[0] == 'P':
        s = s[1:]

    ans = 0
    now = 0
    for i in s:
        if i == 'P':
            now += 1
        else:
            ans = max(ans, now)
            now = 0
    ans = max(ans, now)

    print(ans)


def nex(s):
    l=len(s)
    t=s.copy()
    for i in range(l):
        if(i==0):t[0]=s[0]
        else:
            if(s[i-1]=='A'):t[i]='A'
    return t
t=int(input())
for _ in range(t):
    n=int(input())
    s=list(input())
    c=0
    while(nex(s)!=s):
        s=nex(s)
        c+=1
    print(c)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
# M = mod = 998244353
def factors(n):return sorted(list(set(reduce(list.__add__,([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))))
# def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n').split(' ')]
def li3():return [int(i) for i in input().rstrip('\n')]

for _ in range(val()):
    n = val()
    s = st()
    last = float('inf')
    ans = 0
    for i in range(n):
        
        if s[i] == 'A':
            last = i
        else:
            ans = max(ans,i - last)
    print(ans)


t=int(input())
for i in range(t):
    k=int(input())
    a=input()
    maxlen=0
    cl=-1
    for i in a:
        
        if i=="A":
            cl=0
        elif cl!=-1:
            cl+=1
            maxlen=max(cl,maxlen)
    print(max(maxlen,0))


t=int(input())
for _ in range(t):
	n=int(input())
	a=input()
	ans=0
	for i in range(n):
		if a[i]=='A':
			count=0
			for j in range(i+1,n):
				if a[j]=='P':
					count+=1
				else:
					break
			ans=max(ans,count)
		else:
			continue
	print(ans)


T = int(input())
for i in range(T):
	X = int(input())
	Y = input()
	ans = 0
	count = 0
	start = False
	for j in range(len(Y)):
		if Y[j] == 'A':
			start = True
			ans = max(ans,count)
			count = 0

		else :
			if start :
				count += 1
	ans = max(ans,count)
	print(ans)