【题目描述】

𝐶rying 和 𝑑ino 喜欢玩♂游♂戏。

她们在一棵树上玩游戏，已知树有 n 个点，编号从 1 到 n。第 i 边有一个正 整数边权 𝑤𝑖。

Crying 和 𝑑ino 会在这棵树上玩很多次游戏。每次游戏开始前，清楚姐姐都会给定一个点对 (𝑢,𝑣)，（𝑢,𝑣 为树上不同两点）然后把树上 𝑢 到 𝑣 的路径上所有边的边权拿出来，生成一个数组 𝑆。

𝐶rying 和 𝑑ino 轮流在 𝑆 上进行以最优策略进行游戏，𝐶rying 为先手。 游戏的具体规则是这样的：

1. 𝐶rying 第一次取走一个数。

2. 记上一个人取走的数的值为 𝑥，当前的人需要从 𝑆 中取走一个不大于 𝑥 的数。不能进行操作的人输。

清楚姐姐觉得这个游戏十分地有趣，她想知道，在所有可能的初始点对 (𝑢,𝑣) 中，有多少种情况能使 𝐶rying 有必胜策略。

【输入格式】

本题采用捆绑测试，第一行一个正整数 𝑇，表示数据组数。

对于每一组数据，描述一棵树。

第一行一个正整数 n，表示树的大小。

接下来 n−1 行，每行三个数 𝑢,𝑣,𝑤，代表树上有一条边权为 𝑤 的，连接点 𝑢，点 𝑣 的边。

【输出格式】

对于每组数据，输出一行一个数，表示有多少种初始点对能使 𝐶rying 有必胜策略。

【样例1 输入】

3
5
1 2 2
1 3 1
3 4 1
3 5 2
5
1 2 0
2 3 2
3 4 2
4 5 0
5
1 2 0
1 3 1
3 4 0
3 5 2

【样例1 输出】

9 
8 
10

【样例1 说明】

对于第一组数据，树的形态如下：

可以发现，一共有 (5*2)= 10 种选点对的方案。

当选的点对为 (1,4) 时：

• 𝑆 = {1,1}。
• Crying 取 1，𝑆 = {1}。
• 𝑑ino 取 1，𝑆 = {}。
• 𝐶rying 无法继续操作，𝑑ino 获胜。

可以发现，选其他点对的时候 𝐶rying 均有必胜策略，故最终的答案为 10−1 = 9。

【数据范围】

对于 27% 的数据，n ≤5000。

对于 100% 的数据，1≤ 𝑇 ≤10,1≤ ∑n ≤5 × 10^5 ,1 ≤ 𝑢,𝑣 ≤ n ≤5 × 10^5 ,0≤ 𝑤 ≤ 109 ，保证给定的图是一棵树。