LaTale
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

    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(), the number of cities.
    The following n-1 lines, each contains three integers , , (), the edge of cities.

输出描述:

For each test case print the number of pairs required.
示例1

输入

复制 
2
4
1 2 1
2 3 2
2 4 2
4
1 2 3
2 3 3
2 4 3

输出

复制 
2
6