#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));
	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);
		}
		if(ok) cnt++;
	};
	dfs1(1,0);
	if(cnt==0) ans++;

	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;
			if(in[x][c]>1) cnt++;
			if(in[u][c]==1) cnt--;
			// cout<<x<<' '<<c<<' '<<in[u][c]<<' '<<in[x][c]<<' '<<cnt<<'\n';
			if(cnt==0) ans++;
			dfs2(x,u);
			in[x][c]--,in[u][c]++;
			cnt=t;
		}
	};
	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;
}