3071: LaTale

Legend goes that in the heart of ocean, exists a gorgeous island called $LaTale$, which has $n$ cities. Specially, there is only one way between every two cities. In other words, $n$ cities construct a tree connected by $n-1$ edges. Each of the edges has a weight $w$.

Define $d(u, v)$ the length between city $u$ and city $v$. Under the condition of $u$ differing from $v$, please answer how many pairs$(u, v)$ in which $d(u, v)$ can be divisible by $3$.

Pair(u,v) and pair(v,u) are considered the same.

The first line contains an integer number T, the number of test cases.

For each test case :

The first line contains an integer $n$($2 \leq n \leq 10^{5}$), the number of cities.

The following $n-1$ lines, each contains three integers $u_{i}$, $v_{i}$, $w_{i}$($1 \leq u_{i},v_{i} \leq n, 1 \leq w_{i} \leq 1000$), the edge of cities.

For each test case print the number of pairs required.

2
4
1 2 1
2 3 2
2 4 2
4
1 2 3
2 3 3
2 4 3

2
6