#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define LL long long

const int N = 1e5 + 5;
int T, n, head[N], to[N * 2], nxt[N * 2], len[N * 2], tot, cnt, f[N][30], ans;
bool ban[N];

inline void add(int u, int v, int w){
    to[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
    len[tot] = w;
}

inline void calc(int p){
    bool flag = true;
    for (int i = 0; i < 26; i++){
        if (f[p][i] > 1){
            flag = false;
            break;
        }
    }
    if (!flag && !ban[p]){
        ban[p] = true;
        cnt++;
    }else if (flag && ban[p]){
        ban[p] = false;
        cnt--;
    }
}

void dfs(int p, int fa){
    for (int i = head[p]; i; i = nxt[i]){
        int q = to[i];
        if (q == fa){
            continue;
        }
        f[p][len[i]]++;
        dfs(q, p);
    }
    calc(p);
}

void dfs2(int p, int fa){
    if (!cnt){
        ans++;
    }
    for (int i = head[p]; i; i = nxt[i]){
        int q = to[i];
        if (q == fa){
            continue;
        }
        f[p][len[i]]--;
        f[q][len[i]]++;
        calc(p); calc(q);
        dfs2(q, p);
        f[q][len[i]]--;
        f[p][len[i]]++;
        calc(p); calc(q);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--){
        cin >> n;
        
        for (int i = 1; i <= n; i++){
            ban[i] = head[i] = 0;
            memset(f[i], 0, sizeof(f[i]));
        }
        ans = cnt = tot = 0;

        char ch;
        for (int i = 1, u, v; i < n; i++){
            cin >> u >> v >> ch;
            add(u, v, ch - 'a'); add(v, u, ch - 'a');
        }

        dfs(1, 0);
        dfs2(1, 0);

        cout << ans << endl;
    }

    return 0;
}