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$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nimport math\nfor t in range(int(input())):\n d=int(input())\n s=input()\n k=math.ceil(75*d/100)\n p=s.count("P")\n if k<=p:\n  print(0)\n else:\n  req=k-p\n  c=0\n  for i in range(2,d-2):\n   if s[i]=="A":\n    if "P" in s[i-2:i+1] and "P" in s[i+1:i+3]:\n     c+=1\n   if c==req:\n    print(c)\n    break\n  else:\n   print(-1)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13197