#include <bits/stdc++.h>
using namespace std;
vector<pair<int, char>> g[200005];
int n;
int fa[200005], cnt[200005];
int tot;
void dfs(int x) {
    vector<int> ch[26];
    for (auto [y, c] : g[x]) {
        ch[c - 'a'].push_back(y);
        if (y != fa[x]) {
            fa[y] = x;
            dfs(y);
        }
    }
    for (int c = 0; c < 26; c++) {
        if (ch[c].size() > 2) {
            tot++;
        } else if (ch[c].size() == 2) {
            for (auto y : ch[c]) {
                if (y == fa[x]) {
                    cnt[1]++;
                    cnt[x]--;
                } else {
                    cnt[y]++;
                }
            }
            tot++;
        }
    }
}
void dfs2(int x) {
    for (auto [y, c] : g[x]) {
        if (y != fa[x]) {
            cnt[y] += cnt[x];
            dfs2(y);
        }
    }
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cnt[i] = 0, fa[i] = 0, g[i].clear();
    for (int i = 1; i < n; ++i) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        g[x].push_back({y, c});
        g[y].push_back({x, c});
    }
    tot = 0;
    dfs(1);
    dfs2(1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += cnt[i] == tot;
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}