#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 MAX = 1 << 17;
const int ALP = 26;

vector<int> g[MAX][ALP];
int tin[MAX], tout[MAX], timer;

void dfs(int v, int p) {
	tin[v] = timer++;
	FOR(c, 0, ALP) {
		for (int to : g[v][c]) {
			if (to != p) {
				dfs(to, v);
			}
		}
	}
	tout[v] = timer;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		FOR(i, 0, n - 1) {
			int u, v;
			char c;
			cin >> u >> v >> c;
			u--;
			v--;
			g[u][c - 'a'].push_back(v);
			g[v][c - 'a'].push_back(u);
		}
		timer = 0;
		dfs(0, -1);
		vector<int> pref(n + 1);
		bool bad = false;
		int k = 0;
		FOR(i, 0, n) {
			FOR(c, 0, ALP) {
				if (SZ(g[i][c]) > 2) {
					bad = true;
				}
				else if (SZ(g[i][c]) == 2) {
					for (int j : g[i][c]) {
						if (tin[j] > tin[i]) {
							pref[tin[j]]++;
							pref[tout[j]]--;
						}
						else {
							pref[tin[0]]++;
							pref[tout[0]]--;
							pref[tin[i]]--;
							pref[tout[i]]++;
						}
					}
					k++;
				}
			}
		}
		int ans = 0;
		FOR(i, 0, n) {
			pref[i + 1] += pref[i];
			assert(pref[i] <= k);
			if (pref[i] == k) {
				ans++;
			}
		}
		cout << (bad ? 0 : ans) << "\n";
		FOR(i, 0, n) {
			FOR(c, 0, ALP) {
				g[i][c].clear();
			}
		}
	}
	return 0;
}