#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
const ll mod = 1e9 + 7;
const ll maxn = 2e5 + 5;
ll T;
ll n;
ll ecnt = 0;
ll head[maxn];
ll to[maxn << 1];
ll nxt[maxn << 1];
char w[maxn << 1];
bool vis[maxn << 1];
bool dp[maxn << 1];
void add(ll u, ll v, char ch) {
	++ecnt;
	w[ecnt] = ch;
	nxt[ecnt] = head[u];
	to[ecnt] = v;
	head[u] = ecnt;
}
void clear() {
	for (ll i = 1; i <= n; i++)head[i] = 0;
	for (ll i = 1; i <= ecnt; i++)vis[i] = false;
	ecnt = 0;
}
bool dfs(ll u, ll fa) {
	bool flag = true;
	char ch = '#';
    set<char>q;
	for (ll i = head[u]; i; i = nxt[i]) {
		ll v = to[i];
		if (fa == v)continue;
		if (q.count(w[i]))flag = false;
        q.insert(w[i]);
		if (!vis[i]) {
			vis[i] = true;
			dp[i] &= dfs(v, u);
		}
		flag &= dp[i];
	}
	return flag;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll T; cin >> T;
	while (T--) {
		clear();
		cin >> n;
		for (ll i = 1; i <= n - 1; i++) {
			ll u, v; char ch;
			cin >> u >> v >> ch;
			add(u, v, ch);
			add(v, u, ch);
		}
        for(ll i = 1; i <= ecnt; i++) dp[i] = true;
		ll ans = 0;
		for (ll i = 1; i <= n; i++) if (dfs(i, 0))ans++;
        // for(ll i = 1; i <= n;i++){
        //     for(ll j = head[i]; j; j = nxt[j]){
        //         cout << i << " " << to[j] << " " << dp[j] << endl;
        //     }
        // }
		cout << ans << endl;
	}
}