回顾 Trie（字典树）的定义：

• 大小为 $n$ 的 Trie 是一棵有 $n$ 个顶点和 $(n - 1)$ 条边的有根树，其中每条边都标记有一个字符；
• Trie 中的每个顶点代表一个字符串。设 $s(x)$ 为顶点 $x$ 所代表的字符串；
• Trie 的根代表空字符串。设顶点 $u$ 是顶点 $v$ 的父节点，$c$ 是连接 $u$ 和 $v$ 的边上的字符，则有 $s(v) = s(u) + c$。这里的 $+$ 表示字符串拼接，而非普通的加法运算。

如果每个顶点所代表的字符串互不相同，我们称该 Trie 是合法的。

给定一棵有 $n$ 个顶点和 $(n - 1)$ 条边的无根树，其中每条边都标记有一个字符，问有多少个不同的顶点可以被选为树的根，使得该树成为一棵合法的 Trie？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示树的大小。

接下来的 $(n - 1)$ 行，第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$) 和一个字符 $c_i$，中间用空格隔开，表示存在一条标记为字符 $c_i$ 的边连接顶点 $u_i$ 和 $v_i$。保证 $c_i$ 均为小写英文字母。

保证给定的图是一棵树，且所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示可以选为根以使树成为合法 Trie 的不同顶点的数量。

样例

样例输入 1

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

样例输出 1

2
0

说明

对于第一个样例测试数据，我们只能选择顶点 1 或顶点 2 作为根，否则 $s(1)$ 和 $s(2)$ 将会相同。

对于第二个样例测试数据，无论选择哪个顶点作为根，$s(1)$ 和 $s(2)$，或者 $s(5)$ 和 $s(6)$ 都会相同。