夜晚的街区

题目描述

夜里，Chielo 独自一人徘徊在有 $n$ 个路口、$n - 1$ 个单行道的街区中。所有路口都可以从路口 $1$ 到达，即可以将街区视作一个以节点 $1$ 为根的有向树。每条边都赋有边权，作为这个单行道的路灯亮度。

孤独一人的他，希望知道有多少条经过至少一个单行道的路径，满足所有路灯亮度的二进制与（Bitwise AND）操作的和，和路灯亮度的最小值相等。

一个序列 $a_i$ 的二进制与（Bitwise AND）操作的和 $s$，即将 $a_i$ 每一个数写为二进制，对于二进制的某一位，若所有 $a_i$ 的这一位都是 $1$，则 $s$ 的这一位为 $1$，否则 $s$ 的这一位为 $0$。比如 $$\begin{align} & (30)_{10} \& (7)_{10} \& (31)_{10} \& (22)_{10} \& (14)_{10} \\ = & (11110)_2 \& (00111)_2 \& (11111)_2 \& (10110)_2 \& (01110)_2 \\ = & (00110)_2 \\ = & 6 \end{align}$$

输入

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据：

第一行为一个整数 $n$，表示节点数。

接下来 $(n - 1)$ 行，每行三个空格分隔的整数 $p_i, q_i, w_i$ 表示 $p_i$ 的父节点为 $q_i$，即 $q_i$ 向 $p_i$ 连接一条以 $w_i$ 为路灯亮度的单行道。

保证所有的数据满足 $1 \le T \le 10$, $1 \le n \le {10}^{5}$, $1 \le \sum{n} \le 7.5 \times {10}^{5}$, $1 \le p_i, q_i \le n$, $0 \le w_i \le {10}^{9}$，数据保证给出的有向树是合法的（节点 $1$ 入度为 $0$，其它节点入度为 $1$），并且树的深度不超过 $5 \times {10}^{4}$（根的深度记为 $0$）。

输出

对于每组数据，输出一行，包含一个整数，表示满足边权的二进制与操作的和等于边权的最小值的路径数目。

输入样例

3
5
2 1 3
3 1 9
4 2 1
5 2 5
4
3 2 2
2 1 1
4 3 7
10
2 1 93303
4 1 5
3 2 345
10 3 0
6 4 857
8 2 7
5 10 3138
7 5 4754
9 3 36503968

输出样例

5
4
18

样例解释

第一组数据中，仅有一条路径不符合题意，即 $1 \to 2 \to 5$ 这条路径，其上边权的二进制与操作的和 $3 \& 5 = 1$，最小值 $\min\{3, 5\} = 3$。

第二组数据中，符合题意的路径有 $1 \to 2,$ $2 \to 3,$ $2 \to 3 \to 4$ 和 $3 \to 4$。路径 $1 \to 2 \to 3 \to 4$ 上边权的二进制与操作的和 $1 \& 2 \& 7 = 0$，最小值 $\min\{1, 2, 7\} = 1$。路径 $1 \to 2 \to 3$ 上边权的二进制与操作的和 $1 \& 2 = 0$，最小值 $\min\{1, 2\} = 1$。