#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct node{
	int y,c;
};

void solve(){
	int n;
	cin>>n;
	vector<node> edge[n+1];
	vector in(n+1,vector<int>(30));
	vector<bool> jud(n+1);
	for(int i=1;i<n;i++){
		int u,v;
		char c;
		cin>>u>>v>>c;
		int num=c-'a';
		edge[u].push_back({v,num});
		edge[v].push_back({u,num});
		
		in[u][num]++,in[v][num]++;
	}

	for(int i=1;i<=n;i++){
		for(int j=0;j<30;j++){
			if(in[i][j]>2){
				cout<<"0\n";
				return ;
			}
		}
	}

	int ans=0,cnt=0;
	in.assign(n+1,vector<int>(30));
	function<void(int,int)> dfs1=[&](int u,int p){
		bool ok=false;
		for(auto [x,c]:edge[u]){
			if(x==p) continue;
			in[u][c]++;
			if(in[u][c]>1) ok=true;
			dfs1(x,u);
		}
		jud[u]=ok;
		if(ok) cnt++;
	};
	dfs1(1,0);
	if(cnt==0) ans++;

	auto cal=[&](int u){
		bool ok=false;
		for(int i=0;i<30;i++){
			if(in[u][i]>1) ok=true;
		}
		if(ok&&!jud[u]) cnt++;
		if(!ok&&jud[u]) cnt--;
		jud[u]=ok;
	};

	function<void(int,int)> dfs2=[&](int u,int p){
		for(auto [x,c]:edge[u]){
			if(x==p) continue;
			in[x][c]++,in[u][c]--;
			// int t=cnt;
			cal(x);
			cal(u);
			if(cnt==0) ans++;
			// cout<<u<<' '<<x<<' '<<t<<' '<<cnt<<'\n';
			// for(int i=1;i<=n;i++){
			// 	cout<<i<<' '<<jud[i]<<'\n';
			// }
			dfs2(x,u);
			in[x][c]--,in[u][c]++;
			cal(x);
			cal(u);
		}
	};
	dfs2(1,0);

	cout<<ans<<'\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}