#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define int long long
const int N = 1e6 + 5;
struct node
{
    int val, tag;
} tr[N];
int n;
vector<int> e[N][26];

void build(int p, int l, int r) // 建树
{
    if (l == r)
    {
        tr[p].val = 0;
        tr[p].tag = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    tr[p].val = tr[2 * p].val + tr[2 * p + 1].val;
    tr[p].tag = 0;
}

void push_down(int p, int len)
{
    // cout << p << endl;
    tr[p * 2].tag += tr[p].tag;
    tr[p * 2 + 1].tag += tr[p].tag;
    tr[p * 2].val = tr[2 * p].val + tr[p].tag * (len - len / 2);
    tr[p * 2 + 1].val = tr[p * 2 + 1].val + tr[p].tag * (len / 2); // 右边的区间可能要短一点
    tr[p].tag = 0;
}

void update(int l, int r, int p, int s, int t, int val) // l,r修改区间;s,t查询区间
{
    // cout << s << ' ' << t << endl;
    if (t < l || s > r)
        return;
    if (l <= s && t <= r)
    {
        tr[p].val = tr[p].val + (t - s + 1) * val;
        if (s != t)
            tr[p].tag += val;
        return;
    }
    push_down(p, t - s + 1);
    int mid = (s + t) >> 1;
    update(l, r, 2 * p, s, mid, val);
    update(l, r, 2 * p + 1, mid + 1, t, val);
    tr[p].val = tr[p * 2].val + tr[p * 2 + 1].val;
}

int query(int l, int r, int p, int s, int t)
{
    if (t < l || s > r)
        return 0;
    if (l <= s && t <= r)
        return tr[p].val;
    push_down(p, t - s + 1);
    int mid = (s + t) / 2, ans = 0;
    return query(l, r, 2 * p, s, mid) + query(l, r, 2 * p + 1, mid + 1, t);
}

int dfsn, dfn[N], ls[N], rs[N], f[N];

void dfs(int u, int fa)
{
    f[u] = fa;
    dfn[u] = rs[u] = ls[u] = ++dfsn;
    for (int j = 0; j < 26; j++)
        for (auto to : e[u][j])
        {
            if (to != fa)
            {
                dfs(to, u);
                ls[u] = min(ls[u], ls[to]);
                rs[u] = max(rs[u], rs[to]);
            }
        }
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 26; j++)
            e[i][j].clear();
    for (int i = 1; i < n; i++)
    {
        int x, y;
        char c;
        cin >> x >> y >> c;
        e[x][c - 'a'].push_back(y);
        e[y][c - 'a'].push_back(x);
    }
    bool ok = 0;
    for (int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for (int j = 0; j < 26; j++)
        {
            if (e[i][j].size() >= 3)
            {
                ok = 1;
            }
            else if (e[i][j].size() == 2)
                cnt++;
        }
        if (cnt >= 2)
            ok = 1;
    }
    if (ok)
    {
        cout << 0 << endl;
        return;
    }
    build(1, 1, n);
    dfsn = 0;
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            if (e[i][j].size() == 2)
            {
                for (int k = 0; k < 26; k++)
                {
                    if (k != j)
                    {
                        for (auto to : e[i][k])
                        {
                            if (to != f[i])
                                update(ls[to], rs[to], 1, 1, n, 1);
                            else
                            {
                                update(1, n, 1, 1, n, 1);
                                update(ls[i], rs[i], 1, 1, n, -1);
                            }
                        }
                    }
                }
                update(dfn[i], dfn[i], 1, 1, n, 1);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (query(i, i, 1, 1, n) == 0)
            ans++;
    }
    cout << ans << endl;
}

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

    return 0;
}