#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<std::vector<std::pair<int, char>>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        char c;
        std::cin >> u >> v >> c;
        u--, v--;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }
    
    int need = 0;
    std::vector<int> parent(n, -1), f(n);
    
    auto dfs = [&](auto self, int x) -> void {
        std::vector<int> ch[26];
        for (auto [y, c] : adj[x]) {
            ch[c - 'a'].push_back(y);
            if (y != parent[x]) {
                parent[y] = x;
                self(self, y);
            }
        }
        for (int c = 0; c < 26; c++) {
            if (ch[c].size() > 2) {
                need++;
            } else if (ch[c].size() == 2) {
                for (auto y : ch[c]) {
                    if (y == parent[x]) {
                        f[0]++;
                        f[x]--;
                    } else {
                        f[y]++;
                    }
                }
                need++;
            }
        }
    };
    dfs(dfs, 0);
    
    
    auto dfs1 = [&](auto self, int x) -> void {
        for (auto [y, c] : adj[x]) {
            if (y != parent[x]) {
                f[y] += f[x];
                self(self, y);
            }
        }
    };
    dfs1(dfs1, 0);
    
    int ans = std::count(f.begin(), f.end(), need);
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}