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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 1 << 17;
vector<PII> g[N];
int val[N];
int k = 0;
bool ok = 1;

void dfs1(int v, int par){
	map<int, int> uniq;
	PII para = MP(-1, -1);
	
	for(auto e : g[v]){
		if(uniq.count(e.S))
			para = MP(uniq[e.S], e.F);
		
		uniq[e.S] = e.F;
	}
		
	if(SZ(g[v]) - SZ(uniq) > 1){
		ok = 0;
		return;
	}
	for(auto e : g[v])
		if(e.F != par)
			dfs1(e.F, v);
	if(para.F == -1)
		return;
		
	if(para.F == par || para.S == par){
		int to = (para.F == par) ? para.S : para.F;
		val[0]++;
		val[v]--;
		val[to]++;
		k++;
	}
	else{
		val[para.F]++;
		val[para.S]++;
		k++;
	}
}
int ans = 0;
void dfs2(int v, int par, int va){
	va += val[v];
	if(va == k)
		ans++;
		
	//cout << v << " " <<  va << endl;
	
	for(auto e : g[v])
		if(e.F != par)
			dfs2(e.F, v, va);
	
	va -= val[v];
}

void clear(int n){
	FOR(i, 0, n){
		g[i].clear();
		val[i] = 0;
	}
	k = 0;
	ok = 1;
	ans = 0;
}

void solve(){
	int n;
	cin >> n;
	FOR(i, 0, n - 1){
		int a, b;
		char x;
		cin >> a >> b >> x;
		a--; b--;
		g[a].PB(MP(b, x - 'a'));
		g[b].PB(MP(a, x - 'a'));
	}
	dfs1(0, 0);
	if(ok == 0){
		cout << "0\n";
		clear(n);
		return;
	}
	
	dfs2(0, 0, 0);
	cout << ans << "\n";
	clear(n);
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--)
		solve();
	
	
	return 0;
}