#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);
      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;
        for (auto [u, c] : g[v]) {
          if (u == p) {
            continue;
          }
          if (seen.count(c)) {
            bad[0] += 1;
            bad[pre[v] + 1] -= 1;
            bad[post[v] + 1] += 1;
            bad[n] -= 1;
            break;
          }
          seen.insert(c);
          if (c == pe) {
            bad[pre[v]] += 1;
            bad[pre[v] + 1] -= 1;
            for (auto [uu, cc] : g[v]) {
              if (cc != c) {
                bad[pre[uu]] += 1;
                bad[post[uu] + 1] -= 1;
              }
            }
            break;
          }
        }
      };
      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;
}