1077 : 2019

Description

Bobo 有一棵 $n$ 个点的树，点的编号是 $1,2,\dots ,n$. 树有 $(n-1)$ 条边，第 $i$ 条边的端点是 $a_i$ 和 $b_i$，权值是 $c_i$. 求满足 $u<v$ 的 $(u,v)$ 数量，满足点 $u$ 到点 $v$ 路径上的权值和是 $2019$ 的倍数。

Input

输入文件包含多组数据，请处理到文件结束。

每组数据的第一行包含一个整数 $n$.

接下来 $(n-1)$ 行，其中第 $i$ 行包含三个整数 $a_i$, $b_i$ 和 $c_i$.

• $n\le 2\times {10}^4$
• $1\le a_i,b_i\le n$
• $0\le c_i<2019$
• $n$ 的总和不超过 ${10}^5$.

Output

对于每组数据，输出一个整数，表示所求的值。

Sample

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

2
6
0

Hint

Source

Author

ftiasch