#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int d, na = 0, np = 0, nr = 0;
        cin >> d;
        nr = 0.75*d;
        if(d%4 != 0) nr = nr + 1;
 
        char *s = new char[d+1];
        for(int i = 1; i <= d; i++)
        {
            cin >> s[i];
            if(s[i] == 'P')
            np++;
        }
 
        if(nr <= np)
        {
            cout << "0\n";
        }
        else
        {
            for(int i = 3; i <= d-2; i++)
            {
                if(s[i] == 'A')
                if(s[i-1] == 'P' || s[i-2] == 'P')
                if(s[i+1] == 'P' || s[i+2] == 'P')
                na++;
            }
            int test = na + np;
            if(nr <= test)
            {
                cout << nr - np << "\n";
            }
            else
            {
                cout << "-1\n";
            }
 
        }
 
        cout << endl;
 
    }
    return 0;
}