#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    [&] {
      int n;
      cin >> n;
      vector<vector<pair<int, char>>> g(n);
      for (int i = 0; i < n - 1; i++) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        --x; --y;
        g[x].emplace_back(y, c);
        g[y].emplace_back(x, c);
      }
      for (int i = 0; i < n; i++) {
        map<char, int> cnt;
        int k2 = 0;
        for (auto [_, c] : g[i]) {
          cnt[c] += 1;
          if (cnt[c] == 3) {
            cout << 0 << '\n';
            return;
          }
          if (cnt[c] == 2) {
            k2 += 1;
            if (k2 == 2) {
              cout << 0 << '\n';
              return;
            }
          }
        }
      }
      vector<int> pre(n);
      vector<int> post(n);
      vector<int> order;
      vector<int> bad(n + 1);
      auto Mark = [&](int L, int R) {
        bad[L] += 1;
        bad[R + 1] -= 1;
      };
      function<void(int, int)> Dfs = [&](int v, int p) {
        pre[v] = order.size();
        order.push_back(v);
        char pe = '.';
        for (auto [u, c] : g[v]) {
          if (u == p) {
            pe = c;
            continue;
          }
          Dfs(u, v);
        }
        post[v] = order.size() - 1;
        set<char> seen;
        char dup = '.';
        for (auto [u, c] : g[v]) {
          if (seen.count(c)) {
            dup = c;
            break;
          }
          seen.insert(c);
        }
        if (dup != '.') {
          Mark(pre[v], pre[v]);
          if (pe != dup) {
            Mark(0, pre[v] - 1);
            Mark(post[v] + 1, n - 1);
          }
          for (auto [uu, cc] : g[v]) {
            if (uu == p) {
              continue;
            }
            if (cc != dup) {
              Mark(pre[uu], post[uu]);
            }
          }
        }
      };
      Dfs(0, -1);
      int ret = 0;
      for (int i = 0; i < n; i++) {
        if (bad[i] == 0) {
          ret += 1;
        }
        bad[i + 1] += bad[i];
      }
      cout << ret << '\n';
    }();
  }
  return 0;
}