#include<bits/stdc++.h>

using namespace std;
const int maxm = 1e5+7;
int cnt[maxm][30],cur[maxm][30],dfn[maxm],rk[maxm],R[maxm],ct = 0;
int dif[maxm],sum[maxm];
vector<int>edge[maxm];
vector<array<int,3>>all;
//所有的产生重复的三元组，按照[u,x,y]的顺序排布
void init(int n){
    all.clear();ct = 0;
    for(int i=1;i<=n+3;i++){
        edge[i].clear();
        dif[i] = sum[i] = 0;
        for(int j=0;j<26;j++){
            cnt[i][j] = cur[i][j] = 0;
        }
    }
}
void dfs(int now,int fa){
    dfn[++ct] = now,rk[now] = ct;
    for(auto u:edge[now]){
        if(u == fa) continue;
        dfs(u,now);
    }
    R[now] = ct;
}
void solve(){
    int n;cin>>n;
    init(n);
    for(int i=1;i<n;i++){
        int u,v;char ch;
        cin>>u>>v>>ch;
        cnt[u][ch - 'a']++;
        cnt[v][ch - 'a']++;
        if(cnt[u][ch - 'a'] == 2){
            all.push_back({u,v,cur[u][ch - 'a']});
        }
        if(cnt[v][ch - 'a'] == 2){
            all.push_back({v,u,cur[v][ch - 'a']});
        }
        cur[u][ch - 'a'] = v;
        cur[v][ch - 'a'] = u;
        edge[u].push_back(v);
        edge[v].push_back(u);
        //建树完成
        //我们要得到[u,x,y]这个三元组
    }
    for(int i=1;i<=n;i++){
        //判断是否存在合法解
        int tot = 0;
        for(int j=0;j<26;j++){
            if(cnt[i][j] >= 3){
                cout<<"0\n";
                return;
            }
            else if(cnt[i][j] == 2) ++tot;
        }
        if(tot > 1){
            cout<<"0\n";
            return;
        }
    }
    dfs(1,0);//得到dfs序
    for(auto item:all){
        int u = item[0],x = item[1],y = item[2];
        if(rk[u] < rk[x] and rk[u] < rk[y]){
            //u在最前面 ，这时根节点只能是x或者y的子树
            dif[rk[x]]++;dif[R[x] + 1]--;
            dif[rk[y]]++;dif[R[y] + 1]--;
        }
        else{
            if(rk[x]>rk[y]) swap(x,y);
            //全局+1，u的子树-1，y的子树+1
            dif[1]++;dif[n+1]--;
            dif[rk[u]]--;dif[R[u] + 1]++;
            dif[rk[y]]++;dif[R[y] + 1]--;
        }
    }
    int sz = all.size(),tot = 0;
    for(int i=1;i<=n;i++){
        sum[i] = sum[i-1] + dif[i];
        if(sz == sum[i]){ ++tot;}
    }
    cout<<tot<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}