#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+45;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll konst[3] = {400000ll,400001ll,-800001ll};
ll n;
vector <pair<int,int>> g[N];
ll rsum[N];
bool visited[N];
ll br[N][3];

void citaj(){
    cin >> n;
    for(int i = 1; i < n; i++){
        int u,v;
        char x;
        cin >> u >> v >> x;
        int sta = 0;
        if(x == 'S') sta = 0;
        if(x == 'I') sta = 1;
        if(x == 'O') sta = 2;
        g[u].push_back({v,sta});
        g[v].push_back({u,sta});
    }
}

void generisi3(){
    for(int i = 1; i <= n; i++){
        g[i].clear();
    }
    n = 100;
    for(int i = 1; i < n; i++){
        g[i].push_back({i+1,rnd()%3});
    }
}

void pisitest3(){
    cout << n << endl;
    for(int i = 1; i < n; i++){
        cout << g[i][0].first << " " << g[i][0].second << endl;
    }
}

void dfs(int x,int par){
    for(auto f : g[x]){
        int u = f.first,r = f.second;
        if(u == par) continue;
        rsum[u] = rsum[x]+konst[r];
        dfs(u,x);
    }
}

ll subtask3(){
    ll sum = 0,sol = 0;
    map <ll,ll> mapa;
    mapa[0] = 1;
    for(int i = 1; i < n; i++){
        int r = g[i][0].second;
        sum += konst[r];
        sol += mapa[sum];
        mapa[sum]++;
    }
    return sol;
}

ll brut(){
    ll sol = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){ visited[j] = br[j][0] = br[j][1] = br[j][2] = 0; }
        queue <int> q;
        q.push(i);
        visited[i] = 1;
        while(!q.empty()){
            int u = q.front();
            if(i < u && br[u][0] == br[u][1] && br[u][1] == br[u][2]) sol++;
            q.pop();
            for(auto f : g[u]){
                int v = f.first,r = f.second;
                if(visited[v]) continue;
                br[v][0] = br[u][0]+(r==0);
                br[v][1] = br[u][1]+(r==1);
                br[v][2] = br[u][2]+(r==2);
                visited[v] = 1;
                q.push(v);
            }
        }
    }
    return sol;
}

ll subtask1(){
    int a=0,b=0;
    for(int i = 1; i <= n; i++){
        for(auto f : g[i]){
            if(f.second == 0){
                a = i,b = f.first;
                break;
            }
        }
        if(a) break;
    }

    for(int i = 1; i <= n; i++){
        for(auto f : g[i]){
            br[i][f.second]++;
        }
    }

    ll sol = 0;
    for(auto f : g[a]){
        if(f.first == b || f.second == 0) continue;
        sol += br[f.first][3-f.second];
    }
    for(auto f : g[b]){
        if(f.first == a || f.second == 0) continue;
        sol += br[f.first][3-f.second];
    }
    sol += br[a][1]*br[a][2];

    return sol;
}

ll moje(){
    /*rsum[1] = 0;
    dfs(1,-1);*/

    int brs = 0;
    for(int i = 1; i <= n; i++){
        for(auto f : g[i]){
            brs += (f.second == 0);
        }
    }
    if(brs == 1){
        return subtask1();
    }

    bool treci = 1;
    for(int i = 1; i < n; i++){
        if(g[i].size() != 1 || g[i][0].first != i+1) treci = 0;
    }
    if(treci){
        return subtask3();
    }

    if(n <= 1000){
        return brut();
    }
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int tp = 2;
    int t;

    if(tp != 1) t = 1;
    else cin >> t;

    while(t--){
        if(tp == 0){
            generisi3();
            ll p = moje(),q = brut();
            if(p != q){
                cout << "WA, moje: " << p << " brut: " << q << endl;
                pisitest3();
                return 0;
            }
            else{
                cout << "OK, moje: " << p << " brut: " << q << endl;
            }
        }
        else if(tp == 1){
            citaj();
            cout << moje() << " " << brut() << endl;
        }
        else{
            citaj();
            cout << moje() << endl;
        }
    }
}