#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int maxn=2e5+10;
int dp[8][2],dp2[8][2];
int ans[100][10];
int solve()
{
    int n;cin>>n;
    string s;
    // string s(n,'C');
    cin>>s;
    s="x"+s;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)a[i]=(s[i]=='P');
    for(int j=0;j<8;j++){
        for(int k=0;k<2;k++)dp[j][k]=-inf;
    }
    dp[7][0]=0;
    auto gmax = [&](int &x,int y){
        if(y>x)x=y;
    };
    for(int i=1;i<=n;i++){
        for(int j=0;j<8;j++){
            for(int k=0;k<2;k++)dp2[j][k]=-inf;
        }
        for(int j=0;j<8;j++){
            for(int k=0;k<=1;k++){
                // cout<<"i="<<i<<" j="<<j<<" k="<<k<<" dp="<<dp[i-1][j][k]<<endl;
                if(k==0){
                    for(int ins=0;ins<2;ins++){
                        for(int c1=0;c1<2;c1++){
                            int g=j;
                            string ss="0";
                            ss[0]+=c1;
                            ss.insert(ss.begin()+ins,a[i]+'0');
                            for(auto &it:ss)g=g*2+it-'0';
                            int res=ans[g][5]+dp[j][k];
                            int now=g&7;
                            gmax(dp2[now][k+1],res);
                        }
                    }
                }
                gmax(dp2[(j&3)*2+a[i]][k],dp[j][k]+((j*2+a[i])==2));
            }
        }
        memcpy(dp,dp2,sizeof(dp));
    }    
    int ans=0;
    for(int i=0;i<8;i++){
        for(int j=0;j<2;j++)gmax(ans,dp[i][j]-max(0,j-1));
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    auto cal = [&](string &s){
        int cnt=0;
        for(int i=0;i+3<s.size();i++)cnt+=(s.substr(i,4)=="0010");
        return cnt;
    };
    for(int i=0;i<100;i++){
        for(int len=1;len<=7;len++){
            string s(len,'0');
            for(int j=0;j<len;j++)s[j]+=(i>>j&1);
            reverse(s.begin(),s.end());
            ans[i][len]=cal(s);
        }
    }
    int T;cin>>T;while(T--)cout<<solve()<<"\n";
}
/*
3
3
CCC
5
CCCCP
4
CPCP



1
5
CCCCP
*/