// https://www.youtube.com/watch?v=CrymicX875M
// Angel of mercy
// How did you move me
// Why am I on my feet again

#ifndef ONLINE_JUDGE
#include "templates/debug.hpp"
#else
#define debug(...)
#endif

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

vector<int> prefixFunction(const string& s) {
    int n = s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

vector<array<int, 26>> computeAutomaton(string s) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefixFunction(s);
    vector<array<int, 26>> res(n);
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'A' + c != s[i]) res[i][c] = res[pi[i - 1]][c];
            else res[i][c] = i + ('A' + c == s[i]);
        }
    }
    return res;
}

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    // atmost 2 'C' and 2 'P'
    constexpr int INF = 0x3f3f3f3f;
    string t = "CCPC";
    auto automaton = computeAutomaton(t);
    using T = array<array<int, 4>, 4>;
    T dp;
    for (auto &v: dp) for (auto &v: v) v = -INF;
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        T ndp;
        for (auto &v: ndp) for (auto &v: v) v = -INF;
        for (int cc = 0; cc < 4; cc++) {
            for (int pf = 0; pf < 4; pf++) {
                if (dp[pf][cc] == -INF) continue;
                int val = dp[pf][cc];
                // normal transition
                char c = s[i];
                int npf = automaton[pf][c - 'A'], nval = val;
                if (npf == 4) nval++, npf = 1;
                ndp[npf][cc] = max(ndp[npf][cc], nval);
                // insert a 'C'
                if (cc + 1 < 4) {
                    c = 'C';
                    npf = automaton[pf][c - 'A'], nval = val;
                    if (npf == 4) nval++, npf = 1;
                    dp[npf][cc + 1] = max(dp[npf][cc + 1], nval - cc);
                    c = 'P';
                    npf = automaton[pf][c - 'A'], nval = val;
                    dp[npf][cc + 1] = max(dp[npf][cc + 1], nval - cc);
                }
            }
        }
        dp.swap(ndp);
    }
    for (int cc = 0; cc < 4; cc++) {
        for (int pf = 0; pf < 4; pf++) {
            if (dp[pf][cc] == -INF) continue;
            int val = dp[pf][cc];
            // normal transition
            char c = s[n];
            int npf = automaton[pf][c - 'A'], nval = val;
            if (npf == 4) nval++, npf = 1;
            // insert a 'C'
            if (cc + 1 < 4) {
                c = 'C';
                npf = automaton[pf][c - 'A'], nval = val;
                if (npf == 4) nval++, npf = 1;
                dp[npf][cc + 1] = max(dp[npf][cc + 1], nval - cc);
                c = 'P';
                npf = automaton[pf][c - 'A'], nval = val;
                dp[npf][cc + 1] = max(dp[npf][cc + 1], nval - cc);
            }
        }
    }
    int ans = -INF;
    for (int pf = 0; pf < 4; pf++) {
        for (int cc = 0; cc < 4; cc++) {
            ans = max(ans, dp[pf][cc]);
        }
    }
    cout << ans << '\n';
}
#undef int

// Make bold hypotheses and verify carefully
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    };
}