Bobo has a tree with $n$ vertices, labeled $1, 2, \dots, n$. The tree has $(n - 1)$ edges, where the $i$-th edge connects $a_i$ and $b_i$ with a weight $c_i$. Find the number of pairs $(u, v)$ such that $u < v$ and the sum of weights on the path between $u$ and $v$ is a multiple of $2019$.

Input

The input contains multiple test cases. Process until the end of the file.

Each test case starts with an integer $n$.

The next $(n - 1)$ lines each contain three integers $a_i$, $b_i$, and $c_i$.

• $n \leq 2 \times 10^4$
• $1 \leq a_i, b_i \leq n$
• $0 \leq c_i < 2019$
• The sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output an integer representing the required count.

Examples

Input 1

4
1 2 1
1 3 2018
1 4 1
4
1 2 0
1 3 0
1 4 0
3
1 2 1
2 3 1

Output 1

2
6
0