#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n); i >= 0; i--)

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    for (int i = 0; i < v.size(); i++) {
        os << v[i] << (i == (v.size() - 1) ? "" : ", ");
    }
    os << "]";
    return os;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2> p) {
    os << "{" << p.first << ", " << p.second << "}";
    return os;
}

#include <cassert>
map<char, int> mp{{'C', 0}, {'P', 1}, {'T', 2}, {'U', 3}};

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a(n);
    rep(i, n) a[i] = mp[s[i]];
    int ans = 4;
    rep(_, 2) {
        int cnt[4][n];
        rep(i, 4) rep(j, n) cnt[i][j] = 0;
        rep(i, n) cnt[a[i]][i] = 1;
        rep(i, 4) rep(j, n - 1) cnt[i][j + 1] += cnt[i][j];

        rep(i, n) {
            if (a[i] != 2) continue;
            if (cnt[3][i] == 0) continue;
            if (cnt[0][i] == cnt[0][n - 1]) continue;
            int ok = n - 1;
            int ng = i;
            while (ok - ng > 1) {
                int mid = (ok + ng) / 2;
                if (cnt[0][i] != cnt[0][mid])
                    ok = mid;
                else
                    ng = mid;
            }
            assert(a[ok] == 0);
            if (cnt[1][ok] == cnt[1][i]) continue;
            int tmp = (s[i - 1] == 3 ? 0 : 1) + 2;
            if (a[i + 1] == 1) tmp--;
            if (a[i + 2] == 0) tmp--;
            ans = min(ans, tmp);
        }

        reverse(all(a));
        rep(i, n) a[i] = 3 - a[i];
    }

    cout << (ans == 4 ? -1 : ans) << endl;
}

int main() {
    int t;
    cin >> t;
    while (t > 0) {
        t--;
        solve();
    }
}