#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int cnt,f[N],siz[N],dfn[N],cntt[30],sum[N];
char s[3];
vector<pair<int,int> >v[N];
void add(int x,int y,int z){
	v[x].push_back({y,z});
	v[y].push_back({x,z});
}
void dfs(int u,int fa){
	f[u]=fa;
	siz[u]=1;
	dfn[u]=++cnt;
	for(auto i:v[u]){
		if(i.first!=fa){
			dfs(i.first,u);
			siz[u]+=siz[i.first];
		}
	}
}
void upd(int x,int y){
	sum[x]++;
	sum[y+1]--;
}
int main(){
	int t,n,a,b,pos,all=0,ans=0;
	scanf("%d",&t);
	while(t--){
		all=ans=cnt=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			sum[i]=0;
			v[i].clear();
		}
		for(int i=1;i<=n-1;i++){
			scanf("%d%d%s",&a,&b,s);
			add(a,b,s[0]-'a'+1);
		}
		dfs(1,0);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=26;j++){
				cntt[j]=0;
			}
			for(auto j:v[i]){
				cntt[j.second]++;
			}
			pos=0;
			for(int j=1;j<=26;j++){
				if(cntt[j]>=3){
					printf("0\n");
					goto lass;
				}
				else if(cntt[j]==2){
					if(pos){
						printf("0\n");
						goto lass;
					}
					pos=j;
				}
			}
			if(!pos){
				continue;
			}
			all++;
			for(auto j:v[i]){
				if(j.second==pos){
					if(j.first==f[i]){
						upd(1,dfn[i]-1);
						upd(dfn[i]+siz[i],n);
					}
					else{
						upd(dfn[j.first],dfn[j.first]+siz[j.first]-1);
					}
				}
			}
		}
		for(int i=1;i<=n;i++){
			sum[i]+=sum[i-1];
			if(sum[i]==all){
				ans++;
			}
		}
		printf("%d\n",ans);
		lass:;
	}
}