众所周知，小凯是一位数对统计重度爱好者。
有一天，小凯在梦中跟数对之神交谈时，数对之神抛给了小凯一道题目：
给你一个有 nn 个节点的树，节点编号为 1 ~ n ，每条边都有各自的长度，现在定义 dis(i , j) 表示 i 号节点跟 j 号节点之间的距离对 2 取模之后的结果，问有多少对 ( i,j,k ) 满足, dis(i,j) = dis(j,k) = dis(i,k) , (1 <= i , j , k <= n) ，注意 i,j,k 可以相等。
跟数对之神交谈已经很累了，你能帮小凯解决这个问题吗？
第一行一个正整数 TT ,表示有 TT 组数据。
对于每组数据：
第一行一个正整数 nn，表示节点个数。
接下来n−1n−1行，每行三个正整数u,v,wu,v,w,表示uu跟vv之间有一条长度为ww的边。
对于 100%100% 的数据， 1≤T≤5,1≤n≤5∗105,1≤u,v≤n,1≤w≤1091≤T≤5,1≤n≤5∗105,1≤u,v≤n,1≤w≤109 。
1
3
1 2 3
1 3 49