Description

Recall the definition of a trie:

• A trie of size $n$ is a rooted tree with $n$ vertices and $(n-1)$ edges, where each edge is marked with a character;
• Each vertex in a trie represents a string. Let $s(x)$ be the string vertex $x$ represents;
• The root of the trie represents an empty string. Let vertex $u$ be the parent of vertex $v$, and let $c$ be the character marked on the edge connecting vertex $u$ and $v$, we have $s(v)$ = $s(u) + c$. Here $+$ indicates string concatenation, not the normal addition operation.

We say a trie is valid, if the string each vertex represents is distinct.

Given an unrooted tree with $n$ vertices and $(n-1)$ edges, where each edge is marked with a character, how many different vertices can be selected as the root of the tree so that the tree becomes a valid trie?

Input Format

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the size of the tree.

For the following $(n-1)$ lines, the $i$-th line contains two integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) and a character $c_i$ separated by a space, indicating that there is an edge marked with a character $c_i$ connecting vertex $u_i$ and $v_i$. It's guaranteed that $c_i$ will only be lower-case English letters.

It's guaranteed that the given graph is a tree, and the sum of $n$ of all test cases will not exceed $10^6$.

Output Format

For each test case output one line containing one integer, indicating the number of different vertices that can be selected as the root of the tree to make it a valid trie.

2
6
3 1 a
3 2 a
3 4 b
4 5 c
4 6 d
6
3 1 a
3 2 a
3 4 b
5 4 c
6 4 c

2
0

Hint

For the first sample test case, we can only select vertex 1 or vertex 2 as the root, otherwise $s(1)$ and $s(2)$ will be the same.

For the second sample test case, no matter which vertex we select as the root, $s(1)$ and $s(2)$, or $s(5)$ and $s(6)$ will be the same.