#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define int long long
struct node {
    int v;
    char c;
};

void solve() {
    int n; cin >> n;
    vector<vector<node> > e(n + 1);
    for(int i = 1;i < n;i++) {
        int u, v;
        char c;
        cin >> u >> v >> c;
        e[u].push_back({v, c});
        e[v].push_back({u, c});
    }
    vector<int> vis(n + 1);
    vector<vector<int> > num(n + 1, vector<int> (26));
    vector<char> f(n + 1);
    function<void(int, int)> dfs = [&] (int x, int fa) {
        vector<int> tmp(26);
        bool fg = true;
        for(auto [y, c] : e[x]) {
            if(y == fa) continue;
            f[y] = c;
            tmp[c - 'a']++;
            num[x][c - 'a']++;
            dfs(y, x);
        }
        for(auto [y, c] : e[x]) {
            if(y == fa) continue;
            if(!vis[y]) fg = false;
        }
        int mx = *max_element(tmp.begin(), tmp.end());
        if(mx <= 1 && fg) vis[x] = 1;
    };
    dfs(1, 0);
    int ans = vis[1];
    function<void(int, int)> dfs2 = [&] (int x, int fa) {
        vector<int> tmp(26);
        if(x != 1) tmp[f[x] - 'a']++;
        for(int i = 0;i < 26;i++) tmp[i] += num[x][i];
        vector<int> v;
        for(auto [y, c] : e[x]) {
            if(y == fa) continue;
            if(!vis[y]) v.push_back(y);
        }
        if(!v.empty()) return;
        for(auto [y, c] : e[x]) {
            if(y == fa) continue;
            tmp[c - 'a'] --;
            vector<int> tmp2(26);
            tmp2[c - 'a']++;
            for(int j = 0;j < 26;j++) tmp2[j] += num[y][j];
            if(*max_element(tmp2.begin(), tmp2.end()) <= 1 && *max_element(tmp.begin(), tmp.end()) <= 1) {
                ans++;
            }
            dfs2(y, x);
            tmp[c - 'a']++;
        }
    };
    dfs2(1, 0);
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}