Chef is a brilliant university student that does not attend lectures because he believes that they are boring and coding is life! However, his university follows certain rules and regulations, and a student may only take an exam for a course if he has attended at least 75% of lectures for this course.
Since you are Chef's best friend, you want to help him reach the attendance he needs to take exams. Unfortunately, Chef is still focused on his code and refuses to attend more lectures, so the only option is to have some of his friends mark him as present by proxy. This trick is well-known in the university, but only few have the talent to pull it off.
In a certain course, there is exactly one lesson per day over the course of $D$ days (numbered $1$ through $D$). You are given a string $S$ with length $D$ describing the lessons Chef attended — for each valid $i$, the $i$-th character of this string is either 'A' if Chef was absent on day $i$ or 'P' if Chef was actually present on day $i$.
For each day $d$ when Chef is absent, one of Chef's friends can mark him as present by proxy on this day only if he was present (if he was really present, not just marked as present) on at least one of the previous two days, i.e. days $d-1$ and $d-2$, and on at least one of the following two days, i.e. days $d+1$ and $d+2$. However, it is impossible to mark him as present by proxy on the first two days and the last two days.
Find the minimum number of times Chef has to be marked as present by proxy so that his attendance becomes at least 75% ($0.75$). Chef's attendance is number of days when he was marked as present, either by proxy or by actually being present, divided by $D$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $D$.
- The second line contains a single string $S$ with length $D$.

-----Output-----
For each test case, print a single line containing one integer — the minimum number of times Chef needs to be marked as present by proxy, or $-1$ if it is impossible to make Chef achieve 75% attendance.

-----Constraints-----
- $1 \le T \le 200$
- $1 \le D \le 1,000$
- $S$ contains only characters 'A' and 'P'

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
1
9
PAAPPAPPP

-----Example Output-----
1

-----Explanation-----
Example case 1: With a proxy on the third day, the attendance string is "PAPPPAPPP". Now, Chef's attendance is at least 75%, so the minimum number of times Chef needs to be marked as present by proxy is $1$.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Implementation


Solutions:
import math
t = int(input())
for i in range(t):
	d = int(input())
	attendence = input()
	num = attendence.count('P')
	maxattendence = math.ceil(0.75 * d)
	if maxattendence <= num:
		print('0')
	else:
		totalproxy = 0
		for j in range(2, len(attendence) - 2):
			if attendence[j] == 'A':
				before = attendence[j - 1:j - 3:-1]
				if j == 2:
					before = attendence[0:j]
				after = attendence[j + 1:j + 3]
				if 'P' in after and 'P' in before:
					totalproxy += 1
		if maxattendence - num <= totalproxy:
			print(maxattendence - num)
		else:
			print('-1')


import math
for i in range(int(input())):
	l = int(input())
	a = input()
	p = math.ceil(len(a) * 3 / 4)
	ctp = a.count('P')
	if p - ctp >= 0:
		res = p - ctp
	else:
		res = 0
	for x in range(2, l - 2):
		if ctp < p:
			if a[x] == 'A' and (a[x - 1] == 'P' or a[x - 2] == 'P') and (a[x + 1] == 'P' or a[x + 2] == 'P'):
				ctp += 1
	if ctp < p:
		print(-1)
	else:
		print(res)


t = int(input())
for i in range(0, t):
	d = int(input())
	s = str(input())
	a = len(s)
	n = 0.75 * a
	m = 0
	count = 0
	for j in range(0, len(s)):
		if s[j] == 'P':
			m = m + 1
	for j in range(2, len(s) - 2):
		if m >= n:
			break
		if s[j] == 'A':
			if s[j - 1] == 'P' or s[j - 2] == 'P':
				if s[j + 1] == 'P' or s[j + 2] == 'P':
					m = m + 1
					count = count + 1
	if m < n:
		print('-1')
	else:
		print(count)


n = int(input())
for i in range(n):
	c = 0
	n = int(input())
	x = input()
	count = int(x.count('P') / len(x) * 100)
	if count >= 75:
		print(0)
	else:
		for a in range(2, len(x) - 2):
			if x[a] == 'A':
				if (x[a - 1] == 'P' or x[a - 2] == 'P') and (x[a + 1] == 'P' or x[a + 2] == 'P'):
					c = c + 1
			count = int((x.count('P') + c) / len(x) * 100)
			if count >= 75:
				print(c)
				break
		if count < 75:
			print(-1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	p = s.count('P')
	count = p
	n75 = math.ceil(n * 3 / 4)
	for i in range(2, n - 2):
		if s[i] == 'A':
			if (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				count += 1
	if p >= n75:
		print('0')
	elif count >= n75:
		print(math.ceil(n75 - p))
	else:
		print(-1)


t = int(input())
for _ in range(t):
	d = int(input())
	s = list(input())
	tp = s.count('P')
	if tp / d >= 0.75:
		print(0)
	else:
		count = 0
		for i in range(2, d - 2):
			if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				count += 1
			if (tp + count) / d * 100 >= 75:
				print(count)
				break
		if (tp + count) / d * 100 < 75:
			print(-1)


import math
t = int(input())
for t in range(t):
	d = int(input())
	s = input()
	present = s.count('P')
	if present / len(s) >= 0.75:
		print(0)
	else:
		i = 2
		count = 0
		while i < len(s) - 2:
			if s[i] == 'A':
				if (s[i - 2] == 'P' or s[i - 1] == 'P') and (s[i + 2] == 'P' or s[i + 1] == 'P'):
					count += 1
			i += 1
		if (present + count) / len(s) < 0.75:
			print(-1)
		else:
			ans = math.ceil(len(s) * 0.75) - present
			print(ans)


def abc(l, l1):
	x = l1.count('P')
	tp = x / l
	cp = x / l
	rp = x
	c = 0
	mt = 0
	if tp >= 0.75:
		return 0
	if tp < 0.75 and l <= 4:
		return -1
	elif l > 4 and tp < 0.75:
		while rp / l < 0.75:
			rp = rp + 1
			mt += 1
		for j in range(2, len(l1) - 2):
			if l1[j] == 'A' and (l1[j - 1] == 'P' or l1[j - 2] == 'P') and (l1[j + 1] == 'P' or l1[j + 2] == 'P'):
				l1[j] = 'p'
				c = c + 1
				if c >= mt:
					return c
		if c < rp:
			return -1
t = int(input())
for i in range(t):
	l = int(input())
	s = input()
	l1 = list(s)
	print(abc(l, l1))


for _ in range(int(input())):
	n = int(input())
	output = []
	days = input()
	for day in days:
		output.append(day)
	count = 0
	for i in range(2, n - 1):
		if output.count('P') / n >= 0.75:
			print(count)
			break
		if days[i] == 'A':
			if 'P' in days[i + 1:i + 3] and 'P' in days[i - 2:i]:
				output[i] = 'P'
				count += 1
	else:
		print(-1)


T = int(input())
for i in range(T):
	d = int(input())
	s = input()
	ad = 3 * d / 4
	cou = s.count('P')
	if cou >= ad:
		print(0)
	else:
		proxy = 0
		i = 2
		while cou < ad and i < len(s) - 2:
			if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				cou += 1
				proxy += 1
			i += 1
		if ad > cou:
			print(-1)
		else:
			print(proxy)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	p = s.count('P')
	a = math.ceil(0.75 * n)
	c = 0
	if p >= a:
		print('0')
	else:
		for i in range(2, n - 2):
			if s[i] == 'A' and (s[i - 2] == 'P' or s[i - 1] == 'P') and (s[i + 2] == 'P' or s[i + 1] == 'P'):
				c += 1
		if c + p >= a:
			print(a - p)
		else:
			print('-1')


for _ in range(int(input())):
	d = int(input())
	s = list(input())
	c = s.count('P')
	a = 0
	for i in range(2, d - 2):
		if c / d < 0.75:
			if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				a += 1
				c += 1
				if c / d >= 0.75:
					print(a)
					break
		else:
			print(0)
			break
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	s = input()
	k = int(s.count('P') / len(s) * 100)
	if k >= 75:
		print(0)
	else:
		for j in range(2, len(s) - 2):
			if s[j] == 'A':
				if (s[j - 1] == 'P' or s[j - 2] == 'P') and (s[j + 1] == 'P' or s[j + 2] == 'P'):
					c += 1
			k = int((s.count('P') + c) / len(s) * 100)
			if k >= 75:
				print(c)
				break
		if k < 75:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	p = s.count('P')
	a = n - p
	count = 0
	for i in range(2, n - 2):
		if p / n < 0.75:
			if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				p = p + 1
				count = count + 1
				if p / n >= 0.75:
					print(count)
					break
		else:
			print(0)
			break
	if p / n < 0.75:
		print(-1)


try:
	t = int(input())
	for _ in range(t):
		l = int(input())
		s = list(input())
		ind = 2
		times = 0
		sc = s.count('P')
		for i in range(2, l - 2):
			if sc / l < 0.75:
				if s[i] == 'A':
					if (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
						sc += 1
						times += 1
						if sc / l >= 0.75:
							print(times)
							break
			else:
				print(times)
				break
		if sc / l < 0.75:
			print(-1)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	present_days = n * 75 / 100
	d = input()
	(pre, k) = (d.count('P'), 0)
	if pre >= present_days:
		print(k)
	else:
		for i in range(2, n - 2):
			if d[i] == 'A' and (d[i - 1] == 'P' or d[i - 2] == 'P') and (d[i + 1] == 'P' or d[i + 2] == 'P'):
				k += 1
			if pre + k >= present_days:
				print(k)
				break
		else:
			print(-1)


def Solve(l, n):
	(cnt, present) = (0, 0)
	for i in range(n):
		if l[i] == 'A':
			if i - 2 >= 0 and i + 2 < n:
				if (l[i - 1] == 'P' or l[i - 2] == 'P') and (l[i + 1] == 'P' or l[i + 2] == 'P'):
					cnt = cnt + 1
		else:
			present += 1
	pre = present / n
	k = 0
	while cnt != 0 and pre < 0.75:
		k += 1
		present += 1
		cnt -= 1
		pre = present / n
	if pre < 0.75:
		print(-1)
	else:
		print(k)
for _ in range(int(input())):
	n = int(input())
	l = input()
	Solve(l, n)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = s.count('A')
	b = s.count('P')
	c = 0
	d = 0
	if b / n >= 0.75:
		print(0)
	else:
		while b / n < 0.75:
			b = b + 1
			c = c + 1
		for j in range(2, n - 2):
			if s[j] == 'A' and ((s[j - 1] == 'P' or s[j - 2] == 'P') and (s[j + 1] == 'P' or s[j + 2] == 'P')):
				d = d + 1
		if c > d:
			print(-1)
		else:
			print(c)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count = s.count('P')
	req = math.ceil(n * 75 / 100) - count
	if req <= 0:
		print(0)
		continue
	else:
		c = 0
		for i in range(2, len(s) - 2):
			if s[i - 2:i].count('P') >= 1 and s[i] == 'A' and (s[i + 1:i + 3].count('P') >= 1):
				c += 1
	if c >= req:
		print(req)
	else:
		print(-1)


for t in range(int(input())):
	d = int(input())
	s = input()
	count = 0
	present = s.count('P')
	if present / d > 0.75:
		print(0)
	else:
		for i in range(2, d - 2):
			if s[i] == 'A':
				if (s[i - 2] == 'P' or s[i - 1] == 'P') and (s[i + 2] == 'P' or s[i + 1] == 'P'):
					present += 1
					count = count + 1
					if present / d >= 0.75:
						print(count)
						break
		else:
			print(-1)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	s = input()
	pcount = 0
	for i in range(n):
		if s[i] == 'P':
			pcount += 1
	per = pcount * 100 / n
	if per >= 75:
		print('0')
		continue
	acount = 0
	f = 0
	for i in range(2, n - 2):
		if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
			pcount += 1
			acount += 1
			per = pcount * 100 / n
			if per >= 75:
				f = 1
				print(acount)
				break
	if f == 1:
		continue
	per = pcount * 100 / n
	if per >= 75:
		print(acount)
	else:
		print('-1')


import math
for h in range(int(input())):
	n = int(input())
	mind = 75 * n / 100
	mind = math.ceil(mind)
	s = input()
	ans = s.count('P')
	ans1 = 0
	f = 0
	if ans >= mind:
		print(0)
	else:
		for i in range(2, len(s) - 2):
			if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				ans1 += 1
			if ans1 + ans >= mind:
				print(ans1)
				f = 1
				break
		if f == 0:
			print(-1)


t = int(input())
for _ in range(t):
	d = int(input())
	s = input()
	count = 0
	c = 0
	for i in range(d):
		if i <= 1 or i >= d - 2:
			if s[i] == 'P':
				count += 1
		elif s[i] == 'P':
			count += 1
		elif (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
			c += 1
	if count / d >= 0.75:
		print(0)
	elif (count + c) / d >= 0.75:
		i = 1
		while (count + i) / d < 0.75:
			i += 1
		print(i)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(input())
	c = l.count('P')
	p = c / n * 100
	if p >= 75:
		print('0')
	else:
		count = 0
		q = []
		for j in l:
			q.append(j)
		for j in range(2, n - 2, 1):
			if (l[j - 2] == 'P' or l[j - 1] == 'P') and (l[j + 2] == 'P' or l[j + 1] == 'P') and (l[j] != 'P'):
				q[j] = 'P'
				count += 1
			c = q.count('P')
			p = c / n * 100
			if p >= 75:
				break
		c = q.count('P')
		p = c / n * 100
		if p >= 75:
			print(count)
		else:
			print('-1')


for x in range(int(input())):
	n = int(input())
	l = [*input()]
	i = 0
	c1 = l.count('P')
	c = l.count('P')
	c2 = len(l)
	if c1 / c2 >= 0.75:
		print(0)
	else:
		for y in range(2, len(l) - 2):
			if l[y] == 'A':
				if (l[y - 1] == 'P' or l[y - 2] == 'P') and (l[y + 1] == 'P' or l[y + 2] == 'P'):
					c1 = c1 + 1
					if c1 / c2 >= 0.75:
						print(c1 - c)
						break
		else:
			print(-1)


for _ in range(int(input())):
	d = int(input())
	ip = input()
	var1 = ip.count('P')
	var2 = ip.count('A')
	count = 0
	if d <= 4 and var1 <= var2:
		print(-1)
	elif var1 / d >= 0.75:
		print(0)
	else:
		flag = False
		for i in range(2, d - 2):
			if ip[i] == 'A' and (ip[i - 1] == 'P' or ip[i - 2] == 'P') and (ip[i + 1] == 'P' or ip[i + 2] == 'P'):
				count += 1
				var1 += 1
			if var1 / d >= 0.75:
				flag = True
				break
		if flag is True:
			print(count)
		else:
			print(-1)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	p1 = s.count('P')
	ext = 0
	if n * 0.75 <= p1:
		print(ext)
		continue
	for i in range(2, n - 2):
		if 'P' in s[i - 1] + s[i - 2] and 'P' in s[i + 1] + s[i + 2] and (s[i] == 'A'):
			p1 += 1
			ext += 1
			if n * 0.75 <= p1:
				print(ext)
				break
	else:
		print(-1)


t = int(input())
for _ in range(t):
	d = int(input())
	s = input()
	x = 0
	proxyCount = 0
	for z in s:
		if z == 'P':
			x += 1
	if x / d >= 0.75:
		print(proxyCount)
		continue
	for i in range(2, len(s) - 2):
		if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
			proxyCount += 1
			if (x + proxyCount) / d >= 0.75:
				print(proxyCount)
				break
	if (x + proxyCount) / d < 0.75:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	x = input()
	xd = x.count('P')
	ans = 0
	for i in range(2, n - 2):
		if xd / n < 0.75:
			if x[i] == 'A':
				if (x[i - 1] == 'P' or x[i - 2] == 'P') and (x[i + 1] == 'P' or x[i + 2] == 'P'):
					xd += 1
					ans += 1
					if xd / n >= 0.75:
						break
		else:
			break
	if xd / n < 0.75:
		print(-1)
	else:
		print(ans)


import math
for _ in range(int(input())):
	le = int(input())
	n = input()
	prox = 0
	for i in range(2, len(n) - 2):
		if n[i - 1] == 'P' or n[i - 2] == 'P':
			if n[i + 1] == 'P' or n[i + 2] == 'P':
				if n[i] == 'A':
					prox += 1
	if n.count('P') / le < 0.75:
		prox_min = math.ceil(le * 0.75) - n.count('P')
		if prox_min <= prox:
			print(int(prox_min))
		else:
			print(-1)
	else:
		print(0)


for _ in range(int(input())):
	d = int(input())
	s = input()
	count = 0
	prox = 0
	for i in range(d):
		if i <= 1 or i >= d - 2:
			if s[i] == 'P':
				count += 1
		elif s[i] == 'P':
			count += 1
		elif (s[i - 2] == 'P' or s[i - 1] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
			prox += 1
	if count / d >= 0.75:
		print(0)
	elif (prox + count) / d >= 0.75:
		j = 1
		while (count + j) / d < 0.75:
			j += 1
		print(j)
	else:
		print(-1)


t = input()
for c in range(0, int(t)):
	bp = 0
	d = int(input())
	s = input()
	a = s.count('A')
	p = s.count('P')
	if p / d >= 0.75:
		print('0')
		continue
	for j in range(2, d - 2):
		if s[j] == 'A':
			if (s[j - 1] == 'P' or s[j - 2] == 'P') and (s[j + 1] == 'P' or s[j + 2] == 'P'):
				bp += 1
				p += 1
				if p / d >= 0.75:
					print('\n', bp)
					break
				else:
					continue
	if p / d >= 0.75:
		continue
	else:
		print('-1')


n = int(input())
for i in range(n):
	D = int(input())
	S = input()
	count = 0
	countA = S.count('A')
	countP = S.count('P')
	if D <= 4 and countP <= countA:
		print(-1)
	elif countP / D >= 0.75:
		print(count)
	else:
		f = 0
		for i1 in range(2, len(S) - 2):
			if S[i1] == 'A' and (S[i1 - 2] == 'P' or S[i1 - 1] == 'P') and (S[i1 + 1] == 'P' or S[i1 + 2] == 'P'):
				count += 1
				countP += 1
				if countP / D >= 0.75:
					f = 1
					break
		if f == 1:
			print(count)
		else:
			print(-1)


T = int(input())
while T:
	d = int(input())
	S = input().strip()
	PList = ''
	count = 0
	flag = False
	for i in range(d):
		PList += 'P' if S[i] == 'P' else ''
	if len(PList) / d * 100 >= 75:
		print(0)
	else:
		for i in range(2, d - 2):
			if S[i] == 'A':
				if (S[i - 1] == 'P' or S[i - 2] == 'P') and (S[i + 1] == 'P' or S[i + 2] == 'P'):
					PList += 'P'
					count += 1
			if len(PList) / d * 100 >= 75:
				print(count)
				flag = True
				break
		else:
			print(-1)
	T -= 1


T = int(input())
for i in range(T):
	D = int(input())
	S = list(input())
	p = S.count('P')
	time = 0
	for j in range(2, D - 2):
		if p / D < 0.75:
			if S[j] == 'A' and (S[j - 1] == 'P' or S[j - 2] == 'P') and (S[j + 1] == 'P' or S[j + 2] == 'P'):
				p = p + 1
				time = time + 1
				if p / D >= 0.75:
					print(time)
					break
		else:
			print(0)
			break
	if p / D < 0.75:
		print(-1)


t = int(input())
while t > 0:
	d = int(input())
	s = input()
	ad = 3 * d / 4
	cou = s.count('P')
	if cou >= ad:
		print(0)
	else:
		proxy = 0
		i = 2
		while cou < ad and i < len(s) - 2:
			if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				cou += 1
				proxy += 1
			i += 1
		if ad > cou:
			print(-1)
		else:
			print(proxy)
	t -= 1


t = int(input())
for i in range(t):
	d = int(input())
	l = input()
	count = 0
	for i in l:
		if i == 'P':
			count += 1
	perc = count / d
	num = 0
	pr = 0
	if perc < 0.75:
		for i in range(2, d - 2):
			if l[i] == 'A':
				if (l[i - 1] == 'P' or l[i - 2] == 'P') and (l[i + 1] == 'P' or l[i + 2] == 'P'):
					pr = pr + 1
	while perc < 0.75 and pr > 0:
		pr = pr - 1
		count = count + 1
		num = num + 1
		perc = count / d
	if perc < 0.75:
		print(-1)
	else:
		print(num)


for i in range(int(input())):
	n = int(input())
	l = [x.lower() for x in input()]
	p = l.count('p')
	printed = False
	c = 0
	if n > 3:
		for i in range(2, n - 2):
			if p >= 0.75 * n:
				print(c)
				printed = True
				break
			if (l[i - 1] == 'p' or l[i - 2] == 'p') and (l[i + 1] == 'p' or l[i + 2] == 'p') and (l[i] == 'a'):
				p += 1
				c += 1
	if p >= 0.75 * n and (not printed):
		print(c)
	elif not printed:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	x = n * 0.75
	p = int(x) if x == int(x) else int(x + 1)
	l = input()
	pre = 0
	for i in l:
		if i == 'P':
			pre += 1
	if pre >= p:
		print(0)
	else:
		proxy = 0
		for i in range(2, n - 2):
			if l[i] == 'A' and (l[i - 1] == 'P' or l[i - 2] == 'P') and (l[i + 1] == 'P' or l[i + 2] == 'P'):
				proxy += 1
			if pre + proxy == p:
				break
		if pre + proxy == p:
			print(proxy)
		else:
			print(-1)


import math
for _ in range(int(input())):
	d = int(input())
	s = input()
	half = math.ceil(d / 2)
	m_c = half + math.ceil((d - half) / 2)
	p_c = s.count('P')
	proxcy_count = 0
	possible_flag = 0
	if p_c >= m_c:
		print(0)
	else:
		for i in range(2, d - 2):
			if s[i] == 'A' and 'P' in (s[i - 2], s[i - 1]) and ('P' in (s[i + 1], s[i + 2])):
				proxcy_count = proxcy_count + 1
			if p_c + proxcy_count == m_c:
				print(proxcy_count)
				possible_flag = 1
				break
			possible_flag = 0
		if possible_flag == 0:
			print(-1)


def solve(n, s):
	p = s.count('P')
	ans = 0
	i = 2
	while i < n - 2 and 4 * p < 3 * n:
		if 'P' in {s[i - 1], s[i - 2]} and 'P' in {s[i + 1], s[i + 2]} and (s[i] != 'P'):
			ans += 1
			p += 1
		i += 1
	if 4 * p < 3 * n:
		return -1
	return ans
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(n, s))


from collections import Counter
import math
t = int(input())
for _ in range(t):
	d = int(input())
	s = list(input())
	dic = Counter(s)
	req = int(math.ceil(d * 0.75))
	if dic['P'] >= req:
		print(0)
	else:
		flag = True
		if d <= 4:
			print(-1)
		elif d > 4:
			k = req - dic['P']
			p = 0
			for i in range(2, d - 2):
				if s[i] == 'A' and 'P' in [s[i - 1], s[i - 2]] and ('P' in [s[i + 1], s[i + 2]]):
					p += 1
				if p == k:
					flag = False
					break
			if flag:
				print(-1)
			else:
				print(p)


try:
	t = int(input())
	for i in range(t):
		d = int(input())
		s = list(input())
		p = 0
		a = 0
		for i in range(d):
			if s[i] == 'P':
				a = a + 1
		for i in range(2, d - 2):
			if a / d < 0.75:
				if s[i] == 'A':
					if (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
						p = p + 1
						a = a + 1
			else:
				break
		if a / d >= 0.75:
			print(p)
		else:
			print(-1)
except:
	pass


for i in range(int(input())):
	l = int(input())
	s = input()
	ind = 2
	times = 0
	sc = s.count('P')
	for i in range(2, l - 2):
		if sc / l < 0.75:
			if s[i] == 'A':
				if (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
					sc += 1
					times += 1
					if sc / l >= 0.75:
						print(times)
						break
		else:
			print(times)
			break
	if sc / l < 0.75:
		print(-1)


from collections import Counter
from math import ceil
for _ in range(int(input())):
	d = int(input())
	s = input()
	c = Counter(s)
	re = ceil(0.75 * d)
	ans = 0
	if c['P'] >= re:
		print(ans)
		continue
	for i in range(2, d - 2):
		if s[i] == 'A':
			if (s[i - 2] == 'P' or s[i - 1] == 'P') and (s[i + 2] == 'P' or s[i + 1] == 'P'):
				c['P'] += 1
				ans += 1
			if c['P'] >= re:
				print(ans)
				break
	else:
		print(-1)


from math import ceil
for _ in range(int(input())):
	d = int(input())
	att = input()
	count_abs = 0
	count_proxy = 0
	for i in range(d):
		if att[i] == 'A':
			count_abs += 1
			if i not in [0, 1, d - 2, d - 1] and (att[i - 1] == 'P' or att[i - 2] == 'P') and (att[i + 1] == 'P' or att[i + 2] == 'P'):
				count_proxy += 1
	req_proxy = count_abs - d + ceil(d * 0.75)
	if req_proxy < 0:
		req_proxy = 0
	if req_proxy <= count_proxy:
		print(req_proxy)
	else:
		print('-1')


t = int(input())
import math
for _ in range(t):
	n = int(input())
	inp = input()
	p = inp.count('P')
	if p / n * 100 >= 75:
		print(0)
	else:
		d = 2
		xd = 0
		while d < n - 2:
			if inp[d] == 'A':
				if (inp[d - 2] == 'P' or inp[d - 1] == 'P') and (inp[d + 1] == 'P' or inp[d + 2] == 'P'):
					xd += 1
			d = d + 1
		if (p + xd) / n * 100 >= 75:
			print(math.ceil(len(inp) * 0.75) - p)
		else:
			print(-1)


import math
for _ in range(int(input())):
	d = int(input())
	s = input()
	l = list(s)
	days = math.ceil(0.75 * d)
	lp = l.count('P')
	if lp >= days:
		print('0')
	else:
		count = 0
		for j in range(2, d - 2):
			if l[j] == 'A':
				if l[j - 2] == 'P' or l[j - 1] == 'P':
					if l[j + 1] == 'P' or l[j + 2] == 'P':
						count += 1
						if count == days - lp:
							print(count)
							break
		else:
			print('-1')


for t in range(int(input())):
	d = int(input())
	s = input()
	a = 0
	p = 0
	for i in range(d):
		if i <= 2 or i >= d - 2:
			if s[i] == 'P':
				a += 1
		elif s[i] == 'P':
			a += 1
		elif (s[i - 2] == 'P' or s[i - 1] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
			p += 1
	if a / d >= 0.75:
		print(0)
	elif (a + p) / d >= 0.75:
		j = 1
		while (a + j) / d < 0.75:
			j += 1
		print(j)
	else:
		print(-1)


for _ in range(int(input())):
	D = int(input())
	S = input()
	totalP = S.count('P')
	addedP = 0
	if totalP / D >= 0.75:
		print(0)
	else:
		for j in range(2, D - 2):
			if S[j] == 'A' and (S[j - 1] == 'P' or S[j - 2] == 'P') and (S[j + 1] == 'P' or S[j + 2] == 'P'):
				addedP += 1
				totalP += 1
				if totalP / D >= 0.75:
					print(addedP)
					break
		if totalP / D < 0.75:
			print(-1)


def Solve(l, n):
	(cnt, present) = (0, l.count('P'))
	if present / n >= 0.75:
		print(0)
		return
	for i in range(2, n - 1):
		if l[i] == 'A':
			if i - 2 > -1 and i + 2 < n:
				if (l[i - 1] == 'P' or l[i - 2] == 'P') and (l[i + 1] == 'P' or l[i + 2] == 'P'):
					cnt = cnt + 1
					present += 1
					if present / n >= 0.75:
						print(cnt)
						return
	if present / n >= 0.75:
		print(cnt)
		return
	else:
		print(-1)
for _ in range(int(input())):
	n = int(input())
	l = input()
	Solve(l, n)


import math
for t in range(int(input())):
	d = int(input())
	s = input()
	k = math.ceil(75 * d / 100)
	p = s.count('P')
	if k <= p:
		print(0)
	else:
		req = k - p
		c = 0
		for i in range(2, d - 2):
			if s[i] == 'A':
				if 'P' in s[i - 2:i + 1] and 'P' in s[i + 1:i + 3]:
					c += 1
			if c == req:
				print(c)
				break
		else:
			print(-1)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	att_arr = list(input())
	required_att = math.ceil(length * 3 / 4)
	required_proxy = required_att - att_arr.count('P')
	if required_proxy < 0:
		required_proxy = 0
	possible_proxy = 0
	for j in range(2, length - 2):
		if att_arr[j] == 'A' and ('P' in att_arr[j - 2:j] and 'P' in att_arr[j + 1:j + 3]):
			possible_proxy += 1
		if possible_proxy > required_proxy:
			break
	if possible_proxy < required_proxy:
		print(-1)
	else:
		print(required_proxy)


T = int(input())
for _ in range(T):
	n = int(input())
	L = list(input())
	ap = L.count('P')
	l = 0.75 * n
	if ap >= l:
		print(0)
	else:
		if l % 1 == 0:
			req = (l // 1 - ap) // 1
		else:
			req = (l // 1 - ap + 1) // 1
		ans = 0
		for i in range(2, n - 2):
			if L[i] == 'A':
				if (L[i - 1] == 'P' or L[i - 2] == 'P') and (L[i + 1] == 'P' or L[i + 2] == 'P'):
					ans += 1
		if ans >= req:
			print(int(req))
		else:
			print(-1)


def ceil(num):
	if num % 1 == 0:
		return int(num // 1)
	else:
		return int(num // 1 + 1)
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = 0
	a = []
	for i in range(n):
		if s[i] == 'P':
			p = p + 1
	req = ceil(0.75 * n)
	requirement = req - p
	for i in range(2, n - 2):
		if s[i] == 'A':
			if (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				a.append(i)
	if requirement > len(a):
		print(-1)
	else:
		print(max(requirement, 0))


for t in range(int(input())):
	n = int(input())
	s = input()
	attendence = n * 75 / 100
	present = s.count('P')
	count = 0
	if present >= attendence:
		print(count)
	else:
		for i in range(2, n - 2):
			if s[i] == 'A' and (s[i - 1] == 'P' or s[i - 2] == 'P') and (s[i + 1] == 'P' or s[i + 2] == 'P'):
				count += 1
			if present + count >= attendence:
				print(count)
				break
		else:
			print(-1)